[Solution] Party Codeforces Solution | Solution Codeforces

B. Party

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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,\dots ,n$. If member 𝑖$i$ is not invited, the party will gain an unhappiness value of 𝑎𝑖$a_i$.

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

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 number of cakes eaten is even?

Input

Each test contains multiple test cases. The first line contains the number of test cases 𝑡$t$ (1≤𝑡≤104$1\le t\le {10}^4$). The description of the test cases follows.

The first line of each test case contains two integers 𝑛$n$ and 𝑚$m$ (1≤𝑛≤105$1\le n\le {10}^5$, 0≤𝑚≤min(105,𝑛(𝑛−1)2)$0\le m\le min({10}^5,\frac{n(n-1)}{2})$) — the number of club members and pairs of friends.

Perfect Permutation Codeforces Solution

Party Codeforces Solution

Color the Picture Codeforces Solution

Rain Codeforces Solution

XOR Triangle Codeforces Solution

The second line of each test case contains 𝑛$n$ integers 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (0≤𝑎𝑖≤104$0\le a_i\le {10}^4$) — the unhappiness value array.

Each of the next 𝑚$m$ lines contains two integers 𝑥$x$ and 𝑦$y$ (1≤𝑥,𝑦≤𝑛$1\le x,y\le n$, 𝑥≠𝑦$x\ne 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 105${10}^5$.

Output

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