# [Solution] Party solution codeforces – What is the minimum possible total unhappiness value of the party, respecting the constraint that the total number of cakes eaten is even?

Party solution codeforces – A club plans to hold a party and will invite some of its šnĀ members. TheĀ šnĀ members are identified by the numbersĀ 1,2,ā¦,š1,2,ā¦,n. If memberĀ šiĀ is not invited, the party will gain an unhappiness value ofĀ ššai.

## [Solution] Party solution codeforces

There areĀ šmĀ pairs of friends among theĀ šnĀ 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?

## [Solution] Party solution codeforces

Each test contains multiple test cases. The first line contains the number of test casesĀ š”tĀ (1ā¤š”ā¤1041ā¤tā¤104). The description of the test cases follows.

The first line of each test case contains two integersĀ šnĀ andĀ šmĀ (1ā¤šā¤1051ā¤nā¤105,Ā 0ā¤šā¤min(105,š(šā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Ā šnĀ integersĀ š1,š2,ā¦,šša1,a2,ā¦,anĀ (0ā¤ššā¤1040ā¤aiā¤104) ā the unhappiness value array.

Each of the nextĀ šmĀ lines contains two integersĀ š„xĀ andĀ š¦yĀ (1ā¤š„,š¦ā¤š1ā¤x,yā¤n,Ā š„ā š¦xā y) indicating thatĀ š„xĀ andĀ š¦yĀ are friends. Each unordered pairĀ (š„,š¦)(x,y)Ā appears at most once in each test case.

It is guaranteed that both the sum ofĀ šnĀ and the sum ofĀ šmĀ 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.

## [Solution] Party solution codeforces

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


## [Solution] Party solution codeforces

In the first test case, all members can be invited. So the unhappiness value isĀ 00.

In the second test case, the following options are possible:

• inviteĀ 11Ā andĀ 22Ā (00Ā cakes eaten, unhappiness value equal toĀ 33);
• inviteĀ 22Ā andĀ 33Ā (00Ā cakes eaten, unhappiness value equal toĀ 22);
• invite onlyĀ 11Ā (00Ā cakes eaten, unhappiness value equal toĀ 44);
• invite onlyĀ 22Ā (00Ā cakes eaten, unhappiness value equal toĀ 55);
• invite onlyĀ 33Ā (00Ā cakes eaten, unhappiness value equal toĀ 33);
• invite nobody (00Ā cakes eaten, unhappiness value equal toĀ 66).

The minimum unhappiness value is achieved by invitingĀ 22Ā andĀ 33.In the third test case, inviting membersĀ 3,4,53,4,5Ā generates a valid party with the minimum possible unhappiness value.