COCONUTS - Coconuts

几个士兵在投票，有支持与反对两种选择（投票事件很无趣。。。），每个人有自己的看法，但是他们有时也会为了支持朋友的看法而放弃自己的看法。你需要求出一种方案，使得 违背自己初始看法的人数 与 看法不一致的朋友对数 之和最小。 输入：多组数据。 每组数据第一行包含两个数n,m ，为士兵数与朋友对数（士兵编号为1 至n ）。接下来一行n 个数，第i 个数表示士兵i 的看法，支持为1 ，反对为0 。接下来m 行，每行2 个不同的数i,j ，表示士兵i 与士兵j 是朋友。任何一对朋友不重复出现。 输入结束标志为n = m = 0 输出：对于每组数据，包含1 行，1 个正整数，表示违背自己初始看法的人数 与 看法不一致的朋友对数 之和的最小值。 Translated by @Imagine

A group of n castle guards are voting to determine whether African swallows can carry coconuts. While each guard has his own personal opinion on the matter, a guard will often vote contrary to his beliefs in order to avoid disagreeing with the votes of his friends. You are given a list of guards who either do or do not believe in the coconut-carrying capacity of African swallows, and a list of all pairs of guards who are friends. Your task is to determine how each guard must vote in order to minimize the sum of the total number of disagreements between friends and the total number of guards who must vote against their own beliefs.

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