COCONUTS  Coconuts
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 coconutcarrying 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.
Input
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(n1)/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.
Output
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.
Example
Input: 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 Output: 1 2
hide comments
tobimoraut:
20230614 22:54:51
aguante river


zzy070929:
20220314 01:57:25
why do I WA so many times??!!!


urielguz33:
20200615 06:30:26
Didn't think my solution would work lmao. 

balu_236:
20191126 09:36:29
any clue?? Last edit: 20191126 09:49:31 

kiwi1995:
20160628 18:06:39
i m using c++... tle.....<_> 

Shubham Rawat:
20151217 16:19:44
use fast IO plx. n00b problem setter. 

nqo5p90zat:
20151128 03:22:54
Anyone get this one using Java? I got a bunch of time limit exceeded. 

garvit jain:
20150916 06:05:24
beautiful question:)


fkltcbuy:
20150809 19:31:42
Time limit on this one is very tight! Might need to be careful with what language you choose, and may need to tweak algorithm used for similar problems... 

Raghavendran Ramachandran:
20121126 08:01:39

Added by:  Bin Jin 
Date:  20070722 
Time limit:  0.100s 
Source limit:  5000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: CPP 
Resource:  Pacific NW 2006 