시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB3971177739.487%

문제

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

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

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

입력

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

각 테스트 케이스의 첫째 줄에는 사람의 수 N과 친구 관계의 수 M이 주어진다. (2 ≤ N ≤ 300, 0 ≤ 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+XHVjNzg1XHViODI1XHVjNzQwJm5ic3A7XHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzU4IFx1YzIxOCBOXHVhY2ZjIFx1Y2U1Y1x1YWQ2YyBcdWFkMDBcdWFjYzRcdWM3NTggXHVjMjE4IE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyAzMDAsIDAgJmxlOyBNICZsZTsgTihOLTEpXC8yKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWMwYWNcdWI3OGNcdWM3NTggXHVjMGRkXHVhYzAxXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIDFcdWM3NDAgXHViYmZjXHVkNjAxXHVjNzc0XHVhYzAwIDk5OTlcdWJjODggXHViYjM4XHVjODFjXHViOTdjIFx1ZDQ4MCBcdWMyMTggXHVjNzg4XHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU1YyBcdWMwYWNcdWI3OGMsIDBcdWM3NDAgXHVjNWM2XHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU1YyBcdWMwYWNcdWI3OGNcdWM3NzRcdWIyZTQuIFx1YzgxNVx1YmNmNFx1YjI5NCAxXHViYzg4XHVjMGFjXHViNzhjXHViZDgwXHVkMTMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNlNWNcdWFkNmMgXHVhZDAwXHVhY2M0XHVjNzc4IFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjMGFjXHViNzhjXHVjNzQwIDFcdWJjODhcdWJkODBcdWQxMzAgTlx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgTiA9IE0gPSAwXHVjNzc0XHViYTcwLCBcdWM3NzQgXHVhY2JkXHVjNmIwXHViMjk0IFx1Y2M5OFx1YjlhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YjljOFx1YjJlNCwmbmJzcDtcdWNlNWNcdWFkNmMgXHVjMGFjXHVjNzc0XHVjNWQwIFx1ZDIyY1x1ZDQ1Y1x1ZDU1YyBcdWFjYjBcdWFjZmNcdWFjMDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWFkMDBcdWFjYzRcdWM3NTggXHVjMjE4XHVjNjQwIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWMwZGRcdWFjMDFcdWFjZmMgXHViYzE4XHViMzAwXHViODVjIFx1ZDIyY1x1ZDQ1Y1x1Yjk3YyBcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YzBhY1x1Yjc4YyBcdWMyMThcdWM3NTggXHVkNTY5XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjMGRkXHVhYzAxXHVhY2ZjJm5ic3A7XHViYzE4XHViMzAwXHViODVjIFx1ZDIyY1x1ZDQ1Y1x1Yjk3YyBcdWQ1NThcdWJhNzQgXHViNDE4XHViYTcwLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjMGRkXHVhYzAxXHViMzAwXHViODVjIFx1ZDIyY1x1ZDQ1Y1x1Yjk3YyBcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiOTE2OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNvY29udXRzIiwiZGVzY3JpcHRpb24iOiI8cD5BIGdyb3VwIG9mIG4gY2FzdGxlIGd1YXJkcyBhcmUgdm90aW5nIHRvIGRldGVybWluZSB3aGV0aGVyIEFmcmljYW4gc3dhbGxvd3MgY2FuIGNhcnJ5IGNvY29udXRzLiBXaGlsZSBlYWNoIGd1YXJkIGhhcyBoaXMgb3duIHBlcnNvbmFsIG9waW5pb24gb24gdGhlIG1hdHRlciwgYSBndWFyZCB3aWxsIG9mdGVuIHZvdGUgY29udHJhcnkgdG8gaGlzIGJlbGllZnMgaW4gb3JkZXIgdG8gYXZvaWQgZGlzYWdyZWVpbmcgd2l0aCB0aGUgdm90ZXMgb2YgaGlzIGZyaWVuZHMuPFwvcD5cclxuXHJcbjxwPllvdSBhcmUgZ2l2ZW4gYSBsaXN0IG9mIGd1YXJkcyB3aG8gZWl0aGVyIGRvIG9yIGRvIG5vdCBiZWxpZXZlIGluIHRoZSBjb2NvbnV0LWNhcnJ5aW5nIGNhcGFjaXR5IG9mIEFmcmljYW4gc3dhbGxvd3MsIGFuZCBhIGxpc3Qgb2YgYWxsIHBhaXJzIG9mIGd1YXJkcyB3aG8gYXJlIGZyaWVuZHMuIFlvdXIgdGFzayBpcyB0byBkZXRlcm1pbmUgaG93IGVhY2ggZ3VhcmQgbXVzdCB2b3RlIGluIG9yZGVyIHRvIG1pbmltaXplIHRoZSBzdW0gb2YgdGhlIHRvdGFsIG51bWJlciBvZiBkaXNhZ3JlZW1lbnRzIGJldHdlZW4gZnJpZW5kcyBhbmQgdGhlIHRvdGFsIG51bWJlciBvZiBndWFyZHMgd2hvIG11c3Qgdm90ZSBhZ2FpbnN0IHRoZWlyIG93biBiZWxpZWZzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IHRvIHRoaXMgcHJvYmxlbSB3aWxsIGNvbnRhaW4gbXVsdGlwbGUgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgYmVnaW5zIHdpdGggYSBzaW5nbGUgbGluZSBjb250YWluaW5nIGFuIGludGVnZXIgbiAod2hlcmUgMiAmbGU7IG4gJmxlOyAzMDApLCB0aGUgbnVtYmVyIG9mIGd1YXJkcywgYW5kIGFuIGludGVnZXIgbSAod2hlcmUgMCZuYnNwOyZsZTsgbSAmbGU7IG4obi0xKVwvMiksIHRoZSBudW1iZXIgb2YgcGFpcnMgb2YgZ3VhcmRzIHdobyBhcmUgZnJpZW5kcy4gVGhlIHNlY29uZCBsaW5lIG9mIHRoZSB0ZXN0IGNhc2UgY29udGFpbnMgbiBpbnRlZ2Vycywgd2hlcmUgdGhlIGl0aCBpbnRlZ2VyIGlzIDEgaWYgdGhlIGl0aCBndWFyZCBiZWxpZXZlcyBpbiB0aGUgYWJpbGl0eSBvZiBBZnJpY2FuIHN3YWxsb3dzIHRvIGNhcnJ5IGNvY29udXRzLCBhbmQgMCBvdGhlcndpc2UuIEZpbmFsbHksIHRoZSBuZXh0IG0gbGluZXMgb2YgdGhlIHRlc3QgY2FzZSBlYWNoIGNvbnRhaW4gdHdvIGRpc3RpbmN0IGludGVnZXJzIGkgYW5kIGogKHdoZXJlIDEgJmxlOyBpLCBqICZsZTsgbiksIGluZGljYXRpbmcgdGhhdCBndWFyZHMgaSBhbmQgaiBhcmUgZnJpZW5kcy4gR3VhcmRzIHdpdGhpbiBlYWNoIHBhaXIgb2YgZnJpZW5kcyBtYXkgYmUgbGlzdGVkIGluIGFueSBvcmRlciwgYnV0IG5vIHBhaXIgb2YgZ3VhcmRzIHdpbGwgYmUgcmVwZWF0ZWQuIFRoZSBpbnB1dCBpcyB0ZXJtaW5hdGVkIGJ5IGFuIGludmFsaWQgdGVzdCBjYXNlIHdpdGggbiA9IG0gPSAwLCB3aGljaCBzaG91bGQgbm90IGJlIHByb2Nlc3NlZC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBpbnB1dCB0ZXN0IGNhc2UsIHByaW50IGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyB0aGUgbWluaW11bSBwb3NzaWJsZSBzdW0gb2YgdGhlIHRvdGFsIG51bWJlciBvZiBkaXNhZ3JlZW1lbnRzIGJldHdlZW4gYWxsIGZyaWVuZHMgcGx1cyB0aGUgdG90YWwgbnVtYmVyIG9mIGd1YXJkcyB3aG8gbXVzdCB2b3RlIGFnYWluc3QgdGhlaXIgb3duIGJlbGllZnMuPFwvcD5cclxuIiwiaGludCI6IjxwPkluIHRoZSBmaXJzdCB0ZXN0IGNhc2UsIHRoZSBiZXN0IHJlc3VsdCBpcyBhY2hpZXZlZCB3aGVuIGFsbCBndWFyZHMgdm90ZSB0aGF0IEFmcmljYW4gc3dhbGxvd3MgY2Fubm90IGNhcnJ5IGNvY29udXRzLiBIZXJlLCB0aGVyZSBpcyBvbmx5IGEgcGVuYWx0eSBvZiAxIGZvciB0aGUgZmlyc3QgZ3VhcmQgdm90aW5nIGFnYWluc3QgaGlzIGJlbGllZnMuPFwvcD5cclxuXHJcbjxwPkluIHRoZSBzZWNvbmQgdGVzdCBjYXNlLCB0aGUgYmVzdCByZXN1bHQgaXMgYWNoaWV2ZWQgd2hlbiBlYWNoIGd1YXJkIHZvdGVzIGZvciBoaXMgYmVsaWVmcy4gVGhlIHBlbmFsdHkgb2YgMiBhcmlzZXMgZnJvbSB0aGUgZGlzYWdyZWVtZW50cyBiZXR3ZWVuIGd1YXJkcyAyIGFuZCA0LCBhbmQgZ3VhcmRzIDMgYW5kIDUuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > North America > Pacific Northwest Regional > 2006 Pacific Northwest Region Programming Contest K번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: YunGoon