시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 64 21 12 70.588%

문제

사람들은 민혁이가 9999번 문제를 풀 수 있다와 없다를 가지고 투표를 진행하려고 한다. 사람들은 보통 자신의 생각대로 투표하지만, 가끔 자신의 친구와 의견이 충돌되는 것을 막기 위해서 자신의 생각과 반대로 투표하는 경우도 있다.

민혁이가 9999번 문제를 풀 수 있다고 생각한 사람과 없다고 생각한 사람의 목록이 주어지고, 사람들 사이의 친구 관계가 입력으로 주어진다. 

친구 사이에 투표한 결과가 서로 다른 관계의 수와 자신의 생각과 반대로 투표를 해야 하는 사람 수의 합을 최소로 하기 위해서 각 사람들이 어떻게 투표를 해야 하는지 구하는 프로그램을 작성하시오.

입력

입력을 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 사람의 수 N과 친구 관계의 수 M이 주어진다. (2 ≤ N ≤ 300, 1 ≤ M ≤ N(N-1)/2)

둘째 줄에는 각 사람의 생각을 나타내는 N개의 수가 주어진다. 1은 민혁이가 9999번 문제를 풀 수 있다고 생각한 사람, 0은 없다고 생각한 사람이다. 정보는 1번사람부터 순서대로 주어진다.

다음 M개의 줄에는 친구 관계인 두 사람의 번호가 주어진다. 사람은 1번부터 N번까지 번호가 매겨져 있다.

입력의 마지막 줄에는 N = M = 0이며, 이 경우는 처리하지 않아야 한다.

출력

각 테스트 케이스 마다, 친구 사이에 투표한 결과가 서로 다른 관계의 수와 자신의 생각과 반대로 투표를 해야 하는 사람 수의 합의 최소값을 출력한다.

예제 입력

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

힌트

첫째 테스트 케이스의 경우에 첫 번째 사람이 자신의 생각과 반대로 투표를 하면 되며, 두 번째 경우에는 자신의 생각대로 투표를 하면 된다.