Codeworks round 810 (Div. 2) B.Party super detailed problem solution

Another amazing question for me , I've been struggling with some small details during the game , Didn't do it , After thinking for several days after the game, I finally thought , Should say no codeforces The question is really YYDS;

See if anyone has a solution to this problem , Maybe you think it's too simple hahaha .

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

The question ： A club holds a party , And will invite it n Members , Each member has an unhappy value a[i], If they are not invited, they will be unhappy ,n There are members m To friends （ The description of each pair of friends is unique , There is no repetition ）, Each pair of friends will share a cake , The total number of cakes eaten is equal to the number of invited members of each pair of friends , The total number of cakes required is even , Ask the minimum possible total unhappiness value of the party ？

Ideas ： First we will know , The initial conditions ,m Is the total number of cakes eaten , So we can see directly , When m Even hours at the beginning , Everyone can be invited , Then no one is unhappy , So direct output 0 Just fine .

It is important to m In the case of an odd number , At this time, we want to m Become an even number , Just let m Subtract an odd number , So we need to record everyone in m The number of times a friend appears inside d[x], If the number of times is odd , We'll take ans=min(a[i],ans),（a The array records everyone's unhappy value ）

It's not over here , There's another situation , That is, the sum of the unhappiness values of two people is less than ans, It's an example 3 What happened , Then we will find out , There is another way to make m From odd to even , Is to delete a pair of friends directly （x,y） If and only if d[x] and d[y] When all are even numbers (d The array stores everyone in m For the number of times in a friend ), Why? Here's an explanation ：

When d[x] and d[y] For even when , Delete at the same time x and y,m Still odd , But it's limited here （x,y） It's a pair of friends , So one of them coincides , So in this case m It becomes even .

Will there be three or more friends who have not been invited to make m Become even ？ The answer is no （ I was stuck here at that time ）, Because if there is one of these three or more d【x】 If it's an odd number , This is the first case we discussed , At this time, we can directly choose this x, Because choosing one is always less unhappy than choosing three .

If there is no d[x] If it's an odd number , This is the second case we discussed .

Clear your mind and start knocking ;

#include <bits/stdc++.h>
using namespace std;
int main()
{
    / Salted eggs __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;
}