시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 127 48 27 44.262%

문제

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

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

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

입력

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

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

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

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

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

출력

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

예제 입력 1

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

1
2

힌트

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

W3sicHJvYmxlbV9pZCI6IjkxNjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWIyOTQgOTk5OVx1YmM4OCBcdWJiMzhcdWM4MWNcdWI5N2MgXHVkNDgwIFx1YzIxOCBcdWM3ODhcdWIyZTQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc0MCBcdWJiZmNcdWQ2MDFcdWM3NzRcdWFjMDAgPGEgaHJlZj1cImh0dHBzOlwvXC93d3cuYWNtaWNwYy5uZXRcL3Byb2JsZW1cLzk5OTlcIj45OTk5XHViYzg4IFx1YmIzOFx1YzgxYzxcL2E+XHViOTdjIFx1ZDQ4MCBcdWMyMTggXHVjNzg4XHViMmU0XHVjNjQwIFx1YzVjNlx1YjJlNFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVkMjJjXHVkNDVjXHViOTdjIFx1YzljNFx1ZDU4OVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc0MCBcdWJjZjRcdWQxYjUgXHVjNzkwXHVjMmUwXHVjNzU4IFx1YzBkZFx1YWMwMVx1YjMwMFx1Yjg1YyBcdWQyMmNcdWQ0NWNcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YWMwMFx1YjA1NCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjZTVjXHVhZDZjXHVjNjQwIFx1Yzc1OFx1YWNhY1x1Yzc3NCBcdWNkYTlcdWIzY2NcdWI0MThcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YjljOVx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjNzkwXHVjMmUwXHVjNzU4IFx1YzBkZFx1YWMwMVx1YWNmYyBcdWJjMThcdWIzMDBcdWI4NWMmbmJzcDtcdWQyMmNcdWQ0NWNcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYmZjXHVkNjAxXHVjNzc0XHVhYzAwIDk5OTlcdWJjODggXHViYjM4XHVjODFjXHViOTdjIFx1ZDQ4MCBcdWMyMTggXHVjNzg4XHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU1YyBcdWMwYWNcdWI3OGNcdWFjZmMgXHVjNWM2XHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU1YyBcdWMwYWNcdWI3OGNcdWM3NTggXHViYWE5XHViODVkXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCwgXHVjMGFjXHViNzhjXHViNGU0IFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWNlNWNcdWFkNmMgXHVhZDAwXHVhY2M0XHVhYzAwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1Y2U1Y1x1YWQ2YyBcdWMwYWNcdWM3NzRcdWM1ZDAgXHVkMjJjXHVkNDVjXHVkNTVjIFx1YWNiMFx1YWNmY1x1YWMwMCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YWQwMFx1YWNjNFx1Yzc1OCBcdWMyMThcdWM2NDAgXHVjNzkwXHVjMmUwXHVjNzU4IFx1YzBkZFx1YWMwMVx1YWNmYyBcdWJjMThcdWIzMDBcdWI4NWMgXHVkMjJjXHVkNDVjXHViOTdjIFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjMGFjXHViNzhjIFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3NDQmbmJzcDtcdWNkNWNcdWMxOGNcdWI4NWMgXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWFjMDEgXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0IFx1YzViNFx1YjViYlx1YWM4YyBcdWQyMmNcdWQ0NWNcdWI5N2MgXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NFx1YzljMCZuYnNwO1x1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwJm5ic3A7XHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzU4IFx1YzIxOCBOXHVhY2ZjIFx1Y2U1Y1x1YWQ2YyBcdWFkMDBcdWFjYzRcdWM3NTggXHVjMjE4IE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyAzMDAsIDEgJmxlOyBNICZsZTsgTihOLTEpXC8yKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWMwYWNcdWI3OGNcdWM3NTggXHVjMGRkXHVhYzAxXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIDFcdWM3NDAgXHViYmZjXHVkNjAxXHVjNzc0XHVhYzAwIDk5OTlcdWJjODggXHViYjM4XHVjODFjXHViOTdjIFx1ZDQ4MCBcdWMyMTggXHVjNzg4XHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU1YyBcdWMwYWNcdWI3OGMsIDBcdWM3NDAgXHVjNWM2XHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU1YyBcdWMwYWNcdWI3OGNcdWM3NzRcdWIyZTQuIFx1YzgxNVx1YmNmNFx1YjI5NCAxXHViYzg4XHVjMGFjXHViNzhjXHViZDgwXHVkMTMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNlNWNcdWFkNmMgXHVhZDAwXHVhY2M0XHVjNzc4IFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjMGFjXHViNzhjXHVjNzQwIDFcdWJjODhcdWJkODBcdWQxMzAgTlx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgTiA9IE0gPSAwXHVjNzc0XHViYTcwLCBcdWM3NzQgXHVhY2JkXHVjNmIwXHViMjk0IFx1Y2M5OFx1YjlhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YjljOFx1YjJlNCwmbmJzcDtcdWNlNWNcdWFkNmMgXHVjMGFjXHVjNzc0XHVjNWQwIFx1ZDIyY1x1ZDQ1Y1x1ZDU1YyBcdWFjYjBcdWFjZmNcdWFjMDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWFkMDBcdWFjYzRcdWM3NTggXHVjMjE4XHVjNjQwIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWMwZGRcdWFjMDFcdWFjZmMgXHViYzE4XHViMzAwXHViODVjIFx1ZDIyY1x1ZDQ1Y1x1Yjk3YyBcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YzBhY1x1Yjc4YyBcdWMyMThcdWM3NTggXHVkNTY5XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjMGRkXHVhYzAxXHVhY2ZjJm5ic3A7XHViYzE4XHViMzAwXHViODVjIFx1ZDIyY1x1ZDQ1Y1x1Yjk3YyBcdWQ1NThcdWJhNzQgXHViNDE4XHViYTcwLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjMGRkXHVhYzAxXHViMzAwXHViODVjIFx1ZDIyY1x1ZDQ1Y1x1Yjk3YyBcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTE2OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNvY29udXRzIiwiZGVzY3JpcHRpb24iOiI8cD5BIGdyb3VwIG9mIG4gY2FzdGxlIGd1YXJkcyBhcmUgdm90aW5nIHRvIGRldGVybWluZSB3aGV0aGVyIEFmcmljYW4gc3dhbGxvd3MgY2FuIGNhcnJ5IGNvY29udXRzLiBXaGlsZSBlYWNoIGd1YXJkIGhhcyBoaXMgb3duIHBlcnNvbmFsIG9waW5pb24gb24gdGhlIG1hdHRlciwgYSBndWFyZCB3aWxsIG9mdGVuIHZvdGUgY29udHJhcnkgdG8gaGlzIGJlbGllZnMgaW4gb3JkZXIgdG8gYXZvaWQgZGlzYWdyZWVpbmcgd2l0aCB0aGUgdm90ZXMgb2YgaGlzIGZyaWVuZHMuPFwvcD5cclxuXHJcbjxwPllvdSBhcmUgZ2l2ZW4gYSBsaXN0IG9mIGd1YXJkcyB3aG8gZWl0aGVyIGRvIG9yIGRvIG5vdCBiZWxpZXZlIGluIHRoZSBjb2NvbnV0LWNhcnJ5aW5nIGNhcGFjaXR5IG9mIEFmcmljYW4gc3dhbGxvd3MsIGFuZCBhIGxpc3Qgb2YgYWxsIHBhaXJzIG9mIGd1YXJkcyB3aG8gYXJlIGZyaWVuZHMuIFlvdXIgdGFzayBpcyB0byBkZXRlcm1pbmUgaG93IGVhY2ggZ3VhcmQgbXVzdCB2b3RlIGluIG9yZGVyIHRvIG1pbmltaXplIHRoZSBzdW0gb2YgdGhlIHRvdGFsIG51bWJlciBvZiBkaXNhZ3JlZW1lbnRzIGJldHdlZW4gZnJpZW5kcyBhbmQgdGhlIHRvdGFsIG51bWJlciBvZiBndWFyZHMgd2hvIG11c3Qgdm90ZSBhZ2FpbnN0IHRoZWlyIG93biBiZWxpZWZzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IHRvIHRoaXMgcHJvYmxlbSB3aWxsIGNvbnRhaW4gbXVsdGlwbGUgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgYmVnaW5zIHdpdGggYSBzaW5nbGUgbGluZSBjb250YWluaW5nIGFuIGludGVnZXIgbiAod2hlcmUgMiAmbGU7IG4gJmxlOyAzMDApLCB0aGUgbnVtYmVyIG9mIGd1YXJkcywgYW5kIGFuIGludGVnZXIgbSAod2hlcmUgMSAmbGU7IG0gJmxlOyBuKG4tMSlcLzIpLCB0aGUgbnVtYmVyIG9mIHBhaXJzIG9mIGd1YXJkcyB3aG8gYXJlIGZyaWVuZHMuIFRoZSBzZWNvbmQgbGluZSBvZiB0aGUgdGVzdCBjYXNlIGNvbnRhaW5zIG4gaW50ZWdlcnMsIHdoZXJlIHRoZSBpdGggaW50ZWdlciBpcyAxIGlmIHRoZSBpdGggZ3VhcmQgYmVsaWV2ZXMgaW4gdGhlIGFiaWxpdHkgb2YgQWZyaWNhbiBzd2FsbG93cyB0byBjYXJyeSBjb2NvbnV0cywgYW5kIDAgb3RoZXJ3aXNlLiBGaW5hbGx5LCB0aGUgbmV4dCBtIGxpbmVzIG9mIHRoZSB0ZXN0IGNhc2UgZWFjaCBjb250YWluIHR3byBkaXN0aW5jdCBpbnRlZ2VycyBpIGFuZCBqICh3aGVyZSAxICZsZTsgaSwgaiAmbGU7IG4pLCBpbmRpY2F0aW5nIHRoYXQgZ3VhcmRzIGkgYW5kIGogYXJlIGZyaWVuZHMuIEd1YXJkcyB3aXRoaW4gZWFjaCBwYWlyIG9mIGZyaWVuZHMgbWF5IGJlIGxpc3RlZCBpbiBhbnkgb3JkZXIsIGJ1dCBubyBwYWlyIG9mIGd1YXJkcyB3aWxsIGJlIHJlcGVhdGVkLiBUaGUgaW5wdXQgaXMgdGVybWluYXRlZCBieSBhbiBpbnZhbGlkIHRlc3QgY2FzZSB3aXRoIG4gPSBtID0gMCwgd2hpY2ggc2hvdWxkIG5vdCBiZSBwcm9jZXNzZWQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggaW5wdXQgdGVzdCBjYXNlLCBwcmludCBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgdGhlIG1pbmltdW0gcG9zc2libGUgc3VtIG9mIHRoZSB0b3RhbCBudW1iZXIgb2YgZGlzYWdyZWVtZW50cyBiZXR3ZWVuIGFsbCBmcmllbmRzIHBsdXMgdGhlIHRvdGFsIG51bWJlciBvZiBndWFyZHMgd2hvIG11c3Qgdm90ZSBhZ2FpbnN0IHRoZWlyIG93biBiZWxpZWZzLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5JbiB0aGUgZmlyc3QgdGVzdCBjYXNlLCB0aGUgYmVzdCByZXN1bHQgaXMgYWNoaWV2ZWQgd2hlbiBhbGwgZ3VhcmRzIHZvdGUgdGhhdCBBZnJpY2FuIHN3YWxsb3dzIGNhbm5vdCBjYXJyeSBjb2NvbnV0cy4gSGVyZSwgdGhlcmUgaXMgb25seSBhIHBlbmFsdHkgb2YgMSBmb3IgdGhlIGZpcnN0IGd1YXJkIHZvdGluZyBhZ2FpbnN0IGhpcyBiZWxpZWZzLjxcL3A+XHJcblxyXG48cD5JbiB0aGUgc2Vjb25kIHRlc3QgY2FzZSwgdGhlIGJlc3QgcmVzdWx0IGlzIGFjaGlldmVkIHdoZW4gZWFjaCBndWFyZCB2b3RlcyBmb3IgaGlzIGJlbGllZnMuIFRoZSBwZW5hbHR5IG9mIDIgYXJpc2VzIGZyb20gdGhlIGRpc2FncmVlbWVudHMgYmV0d2VlbiBndWFyZHMgMiBhbmQgNCwgYW5kIGd1YXJkcyAzIGFuZCA1LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d