1611. Coconuts

输入格式

The input to this problem will contain multiple test cases. Each test case begins with a single line containing an integer n (where 2 <= n <= 300), the number of guards, and an integer m (where 1 <= m <= n(n-1)/2), the number of pairs of guards who are friends. The second line of the test case contains n integers, where the ith integer is 1 if the ith guard believes in the ability of African swallows to carry coconuts, and 0 otherwise. Finally, the next m lines of the test case each contain two distinct integers i and j (where 1 <= i, j <= n), indicating that guards i and j are friends. Guards within each pair of friends may be listed in any order, but no pair of guards will be repeated. The input is terminated by an invalid test case with n = m = 0, which should not be processed.

输出格式

For each input test case, print a single line containing the minimum possible sum of the total number of disagreements between all friends plus the total number of guards who must vote against their own beliefs.

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

1
2
Notes:
In the first test case, the best result is achieved when all guards vote that African swallows cannot carry coconuts. Here, there is only a penalty of 1 for the first guard voting against his beliefs.
In the second test case, the best result is achieved when each guard votes for his beliefs. The penalty of 2 arises from the disagreements between guards 2 and 4, and guards 3 and 5.