Codeforces Round ＃810 (Div. 2)B.party(思维题)超详细题解

又是一道令我叹为观止的题，比赛的时候一直在纠结一些小细节，没有做出来，赛后想了好几天终于想到了，该说不说codeforces出的题真的是YYDS;

看到没人出这个题的题解，可能是大家觉得太简单了哈哈哈。

A club plans to hold a party and will invite some of its nn members. The nn members are identified by the numbers 1,2,…,n1,2,…,n. If member ii is not invited, the party will gain an unhappiness value of aiai.

There are mm pairs of friends among the nn members. As per tradition, if both people from a friend pair are invited, they will share a cake at the party. The total number of cakes eaten will be equal to the number of pairs of friends such that both members have been invited.

However, the club's oven can only cook two cakes at a time. So, the club demands that the total number of cakes eaten is an even number.

What is the minimum possible total unhappiness value of the party, respecting the constraint that the total number of cakes eaten is even?

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤1041≤t≤104). The description of the test cases follows.

The first line of each test case contains two integers nn and mm (1≤n≤1051≤n≤105, 0≤m≤min(105,n(n−1)2)0≤m≤min(105,n(n−1)2)) — the number of club members and pairs of friends.

The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (0≤ai≤1040≤ai≤104) — the unhappiness value array.

Each of the next mm lines contains two integers xx and yy (1≤x,y≤n1≤x,y≤n, x≠yx≠y) indicating that xx and yy are friends. Each unordered pair (x,y)(x,y) appears at most once in each test case.

It is guaranteed that both the sum of nn and the sum of mm over all test cases do not exceed 105105.

Output

For each test case, print a line containing a single integer – the minimum possible unhappiness value of a valid party.

Example

input

Copy

4
1 0
1
3 1
2 1 3
1 3
5 5
1 2 3 4 5
1 2
1 3
1 4
1 5
2 3
5 5
1 1 1 1 1
1 2
2 3
3 4
4 5
5 1

output

Copy

0
2
3
2

题意： 一个俱乐部举办一个派对，并会邀请它的n个成员，每个成员有一个不开心值a[i],如果他们没有被邀请他们就会不开心，n个成员里面有m对朋友（每对朋友的描述都是独一无二的，就是没有重复的），每对朋友会分享一个蛋糕，吃的蛋糕的总数等于每对朋友的两个成员都被邀请的数量，要求吃的蛋糕总数为偶数，求聚会的最小可能总不快乐值是多少？

思路：首先我们会知道，初始情况，m就是吃的蛋糕总数，所以我们可以直接看出，当m一开始就是偶数时，所有人都可以被邀请，那就没人不开心，所以直接输出0就好。

重要的是m为奇数的情况，这时我们想要把m变成偶数，就要让m减去一个奇数，所以我们需要记录每个人在m个朋友对里面出现的次数d[x]，如果次数是奇数，我们就取ans=min(a[i],ans),（a数组记录每个人的不开心值）

到这里还没结束，还有一种情况，就是两个人加起来的不开心值的和小于ans,就是样例3出现的情况，这时我们会发现，还有一种方法可以让m从奇数变成偶数，就是直接删去一对朋友（x,y）当且仅当d[x]和d[y]均为偶数时(d数组存的是每个人在m对个朋友里面出现的次数)，为什么呢这里解释一下：

当d[x]和d[y]为偶数时，同时删去x和y，m仍然是奇数的，但是这里限定了（x,y）是一对朋友，所以他们有一个是重合的，因此这种情况下m就变成偶数了。

那会不会有三个及三个以上的朋友没被邀请从而使m变成偶数呢？答案是不会（当时我就卡在这里了），因为如果这三个及三个以上里面有一个d【x】是奇数的话，就是我们讨论的第一种情况，这时我们可以直接选择这个x,因为选择一个总比选择三个的不开心值小。

如果里面没有d[x]是奇数的话，就是我们讨论的第二种情况了。

思路理清就可以开始敲了；

#include <bits/stdc++.h>
using namespace std;
int main()
{
    /咸蛋__dd
    int t,n,m,i;
    int dd[100010],y[100010],x[100010],a[100010];
    scanf("%d",&t);
    while(t--)
    {
        memset(dd,0,sizeof(dd));
        scanf("%d %d",&n,&m);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(i=1;i<=m;i++)
        {
            scanf("%d %d",&x[i],&y[i]);
            dd[x[i]]++;
            dd[y[i]]++;
        }int ans=0x3f3f3f3f;
        if(m%2==0)
        {
            printf("0\n");
        }
        else
        {

            for(i=1;i<=n;i++)
            {
                if(dd[i]%2==1)
                    ans=min(ans,a[i]);
            }
            for(i=1;i<=m;i++)
            {
                if(dd[x[i]]%2==0&&dd[y[i]]%2==0)
                    ans=min(ans,a[x[i]]+a[y[i]]);
            }printf("%d\n",ans);
        }


    }
    return 0;
}