시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 8 7 6 100.000%

문제

어제 자유시간에 혼자 위닝을 하면서 자신의 실력을 자랑하던 주호는 강조교한테 편안하게 버스를 타고 말았다.

이에 화가 난 주호는 공부에 대한 생각도 잊은채 위닝을 연습하기로 결심하였다. 하지만 수업시간에 컴퓨터로 직접 하는것이 힘들었기 때문에 바깥에서 N개의 돌멩이로 전략을 세우기로 결심하였다.

주호는 연구한 끝에 자신의 가장 큰 약점은 패스라는 것을 깨달았다. 결국 적절하게 돌멩이를 배치한 다음 효율적으로 패스하는 법을 연구하기로 했는데….

N개의 돌멩이들이 있고  상호간에 패스가 가능한 쌍들이 있다. 즉 모든 쌍들 사이에 패스가 가능한 것이 아니다.

주호는 이 돌멩이들을 적절하게 공격 그룹과 수비 그룹의 두 그룹으로 나누고자 한다. 하지만 패스가 효율적으로 이루어지기 위해서는 각각의 돌멩이들에 대해, 자신과 같은 그룹에 속해 있으면서 패스가 가능한 돌멩이들의 수가 짝수가 되어야 한다. 결국 주호의 목적은 이 조건을 만족하는 총 돌멩이의 숫자가 최대 몇 개인지 알아내는 것이다.

입력

첫 번째 줄에 돌멩이의 개수 N(1 <= N <= 200)이 주어진다. 그 다음 i+1번째 줄에 i번째 돌멩이가 패스할 수 있는 돌멩이의 개수 Li가 들어온다. 그리고 그 다음 각각의 줄에 Li개의 패스 가능한 돌멩이에 해당하는 숫자가 들어온다. 단 각각의 돌멩이들이 자신에게 패스하는 경우는 없고, A 돌멩이가 B 돌멩이의 패스가 가능하다면 B도 A에게 패스가 가능하다고 하자.

출력

첫 번째 줄에 공격이나 수비 중 한쪽 그룹에 속한 돌멩이의 개수 M이 출력된다. 그리고 그 다음 줄에 그 그룹에 속한 돌멩이에 해당하는 숫자를 출력한다. 출력되지 않은 숫자는 반대편 그룹에 속하는 것으로 한다. 여러 가지 해가 존재하는 경우 그 중 하나만 출력하면 된다.

예제 입력 1

5
3 2 3 4
2 1 3
4 2 1 4 5
2 1 3
1 3

예제 출력 1

3
1 2 3
W3sicHJvYmxlbV9pZCI6IjE5MTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3MDRcdWIyZGQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzViNFx1YzgxYyBcdWM3OTBcdWM3MjBcdWMyZGNcdWFjMDRcdWM1ZDAgXHVkNjNjXHVjNzkwIFx1YzcwNFx1YjJkZFx1Yzc0NCBcdWQ1NThcdWJhNzRcdWMxMWMgXHVjNzkwXHVjMmUwXHVjNzU4IFx1YzJlNFx1YjgyNVx1Yzc0NCBcdWM3OTBcdWI3OTFcdWQ1NThcdWIzNTggXHVjOGZjXHVkNjM4XHViMjk0IFx1YWMxNVx1Yzg3MFx1YWQ1MFx1ZDU1Y1x1ZDE0YyBcdWQzYjhcdWM1NDhcdWQ1NThcdWFjOGMgXHViYzg0XHVjMmE0XHViOTdjIFx1ZDBjMFx1YWNlMCBcdWI5ZDBcdWM1NThcdWIyZTQuPFwvcD48cD5cdWM3NzRcdWM1ZDAgXHVkNjU0XHVhYzAwIFx1YjA5YyBcdWM4ZmNcdWQ2MzhcdWIyOTQgXHVhY2Y1XHViZDgwXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWMwZGRcdWFjMDFcdWIzYzQgXHVjNzhhXHVjNzQwXHVjYzQ0IFx1YzcwNFx1YjJkZFx1Yzc0NCBcdWM1ZjBcdWMyYjVcdWQ1NThcdWFlMzBcdWI4NWMgXHVhY2IwXHVjMmVjXHVkNTU4XHVjNjAwXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHVjMjE4XHVjNWM1XHVjMmRjXHVhYzA0XHVjNWQwIFx1Y2VmNFx1ZDRlOFx1ZDEzMFx1Yjg1YyBcdWM5YzFcdWM4MTEgXHVkNTU4XHViMjk0XHVhYzgzXHVjNzc0IFx1ZDc5OFx1YjRlNFx1YzVjOFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHViYzE0XHVhZTY1XHVjNWQwXHVjMTFjIE5cdWFjMWNcdWM3NTggXHViM2NjXHViYTY5XHVjNzc0XHViODVjIFx1YzgwNFx1YjdiNVx1Yzc0NCBcdWMxMzhcdWM2YjBcdWFlMzBcdWI4NWMgXHVhY2IwXHVjMmVjXHVkNTU4XHVjNjAwXHViMmU0LjxcL3A+XHJcbjxwPlx1YzhmY1x1ZDYzOFx1YjI5NCBcdWM1ZjBcdWFkNmNcdWQ1NWMgXHViMDVkXHVjNWQwIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YzU3ZFx1YzgxMFx1Yzc0MCBcdWQzMjhcdWMyYTRcdWI3N2NcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YWU2OFx1YjJlY1x1YzU1OFx1YjJlNC4gXHVhY2IwXHVhZDZkIFx1YzgwMVx1YzgwOFx1ZDU1OFx1YWM4YyBcdWIzY2NcdWJhNjlcdWM3NzRcdWI5N2MgXHViYzMwXHVjZTU4XHVkNTVjIFx1YjJlNFx1Yzc0YyBcdWQ2YThcdWM3MjhcdWM4MDFcdWM3M2NcdWI4NWMgXHVkMzI4XHVjMmE0XHVkNTU4XHViMjk0IFx1YmM5NVx1Yzc0NCBcdWM1ZjBcdWFkNmNcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTg4XHViMjk0XHViMzcwJmhlbGxpcDsuPFwvcD5cclxuPHA+Tlx1YWMxY1x1Yzc1OCBcdWIzY2NcdWJhNjlcdWM3NzRcdWI0ZTRcdWM3NzQgXHVjNzg4XHVhY2UwJm5ic3A7IFx1YzBjMVx1ZDYzOFx1YWMwNFx1YzVkMCBcdWQzMjhcdWMyYTRcdWFjMDAgXHVhYzAwXHViMmE1XHVkNTVjIFx1YzMwZFx1YjRlNFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1Yzk4OSBcdWJhYThcdWI0ZTAgXHVjMzBkXHViNGU0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWQzMjhcdWMyYTRcdWFjMDAgXHVhYzAwXHViMmE1XHVkNTVjIFx1YWM4M1x1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQuPFwvcD5cclxuPHA+XHVjOGZjXHVkNjM4XHViMjk0IFx1Yzc3NCBcdWIzY2NcdWJhNjlcdWM3NzRcdWI0ZTRcdWM3NDQgXHVjODAxXHVjODA4XHVkNTU4XHVhYzhjIFx1YWNmNVx1YWNhOSBcdWFkZjhcdWI4ZjlcdWFjZmMgXHVjMjE4XHViZTQ0IFx1YWRmOFx1YjhmOVx1Yzc1OCBcdWI0NTAgXHVhZGY4XHViOGY5XHVjNzNjXHViODVjIFx1YjA5OFx1YjIwNFx1YWNlMFx1Yzc5MCBcdWQ1NWNcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWQzMjhcdWMyYTRcdWFjMDAgXHVkNmE4XHVjNzI4XHVjODAxXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljMFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWNcdWIyOTQgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YjNjY1x1YmE2OVx1Yzc3NFx1YjRlNFx1YzVkMCBcdWIzMDBcdWQ1NzQsIFx1Yzc5MFx1YzJlMFx1YWNmYyBcdWFjMTlcdWM3NDAgXHVhZGY4XHViOGY5XHVjNWQwIFx1YzE4ZFx1ZDU3NCBcdWM3ODhcdWM3M2NcdWJhNzRcdWMxMWMgXHVkMzI4XHVjMmE0XHVhYzAwIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWIzY2NcdWJhNjlcdWM3NzRcdWI0ZTRcdWM3NTggXHVjMjE4XHVhYzAwIFx1YzlkZFx1YzIxOFx1YWMwMCBcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFjYjBcdWFkNmQgXHVjOGZjXHVkNjM4XHVjNzU4IFx1YmFhOVx1YzgwMVx1Yzc0MCBcdWM3NzQgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWNkMWQgXHViM2NjXHViYTY5XHVjNzc0XHVjNzU4IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWNkNWNcdWIzMDAgXHViYTg3IFx1YWMxY1x1Yzc3OFx1YzljMCBcdWM1NGNcdWM1NDRcdWIwYjRcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+IiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIzY2NcdWJhNjlcdWM3NzRcdWM3NTggXHVhYzFjXHVjMjE4IE4oMSAmbHQ7PSBOICZsdDs9IDIwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIGkrMVx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgaVx1YmM4OFx1YzlmOCBcdWIzY2NcdWJhNjlcdWM3NzRcdWFjMDAgXHVkMzI4XHVjMmE0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViM2NjXHViYTY5XHVjNzc0XHVjNzU4IFx1YWMxY1x1YzIxOCBMaVx1YWMwMCBcdWI0ZTRcdWM1YjRcdWM2MjhcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWFkZjggXHViMmU0XHVjNzRjIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM5MDRcdWM1ZDAgTGlcdWFjMWNcdWM3NTggXHVkMzI4XHVjMmE0IFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWIzY2NcdWJhNjlcdWM3NzRcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWI0ZTRcdWM1YjRcdWM2MjhcdWIyZTQuIFx1YjJlOCBcdWFjMDFcdWFjMDFcdWM3NTggXHViM2NjXHViYTY5XHVjNzc0XHViNGU0XHVjNzc0IFx1Yzc5MFx1YzJlMFx1YzVkMFx1YWM4YyBcdWQzMjhcdWMyYTRcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YWNlMCwgQSBcdWIzY2NcdWJhNjlcdWM3NzRcdWFjMDAgQiBcdWIzY2NcdWJhNjlcdWM3NzRcdWM3NTggXHVkMzI4XHVjMmE0XHVhYzAwIFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNFx1YmE3NCBCXHViM2M0IEFcdWM1ZDBcdWFjOGMgXHVkMzI4XHVjMmE0XHVhYzAwIFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAuPFwvcD4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjZjVcdWFjYTlcdWM3NzRcdWIwOTggXHVjMjE4XHViZTQ0IFx1YzkxMSBcdWQ1NWNcdWNhYmQgXHVhZGY4XHViOGY5XHVjNWQwIFx1YzE4ZFx1ZDU1YyBcdWIzY2NcdWJhNjlcdWM3NzRcdWM3NTggXHVhYzFjXHVjMjE4IE1cdWM3NzQgXHVjZDljXHViODI1XHViNDFjXHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDAgXHVhZGY4IFx1YWRmOFx1YjhmOVx1YzVkMCBcdWMxOGRcdWQ1NWMgXHViM2NjXHViYTY5XHVjNzc0XHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWNkOWNcdWI4MjVcdWI0MThcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWJjMThcdWIzMDBcdWQzYjggXHVhZGY4XHViOGY5XHVjNWQwIFx1YzE4ZFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3M2NcdWI4NWMgXHVkNTVjXHViMmU0LiBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwIFx1ZDU3NFx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwIFx1YWRmOCBcdWM5MTEgXHVkNTU4XHViMDk4XHViOWNjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE5MTAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUd28gUGFydGllcyIsImRlc2NyaXB0aW9uIjoiPHA+S2luZyBCeXRlYXNhciBoYXMgZGVjaWRlZCB0byB0aHJvdyB0d28gZ3JlYXQgcGFydGllcyBhbmQgd2FudHMgdG8gaW52aXRlIHRvIHRoZW0gZXZlcnkgc2luZ2xlIEJ5dGVvdGlhbiBpbmhhYml0YW50LiBPZiBjb3Vyc2UgaGUgd2FudHMgdG8gaW52aXRlIGVhY2ggb2YgdGhlbSB0byBleGFjdGx5IG9uZSBvZiB0aGUgcGFydGllcy4gVGhlIGtpbmcga25vd3MgZnJvbSBoaXMgb3duIHZhc3QgZXhwZXJpZW5jZSB0aGF0IGEgcGVyc29uIGlzIGhhdmluZyBhIGdvb2QgdGltZSB3aGVuIHRoZXJlIGlzIGFuIGV2ZW4gbnVtYmVyIG9mIGhlclwvaGlzIGZyaWVuZHMgYXQgdGhlIHBhcnR5LiBUaHVzIGhlIGhhcyBhc2tlZCB5b3UgdG8gZGl2aWRlIHRoZSBjb3VudHJ5JiMzOTtzIGluaGFiaXRhbnRzIGJldHdlZW4gdHdvIHBhcnRpZXMgaW4gYSB3YXkgdGhhdCBhcyBtYW55IHBlb3BsZSBhcyBwb3NzaWJsZSBoYXZlIGFuIGV2ZW4gbnVtYmVyIG9mIGZyaWVuZHMgYXQgdGhlaXIgcGFydHkuIEEgdHJpdmlhbCBkaXZpc2lvbiwgaS5lLiBvbmUgdGhhdCBsZWF2ZXMgb25lIHBhcnR5IHdpdGggbm8gZ3Vlc3RzIGludml0ZWQsIGlzIGFsbG93ZWQuIFRoZSBhY3F1YWludGFuY2VzaGlwIGlzIGEgc3ltbWV0cmljIHJlbGF0aW9uLCBpLmUuIHdoZW5ldmVyIGEgcGVyc29uIEEga25vd3MgdGhlIHBlcnNvbiBCLCB0aGUgcGVyc29uIEIgYWxzbyBrbm93cyB0aGUgcGVyc29uIEEuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbW1lIHRoYXQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+cmVhZHMgZnJvbSB0aGUgc3RhbmRhcmQgaW5wdXQgdGhlIG51bWJlciBvZiBCeXRlb3RpYSYjMzk7cyBpbmhhYml0YW50cyBhbmQgdGhlIGRlc2NyaXB0aW9uIG9mIHRoZWlyIGFjcXVhaW50YW5jZXMsPFwvbGk+XHJcblx0PGxpPnNwbGl0cyB0aGUgaW5oYWJpdGFudHMgaW50byB0d28gcGFydGllcyBpbiBzdWNoIHdheSB0aGF0IHRoZSBudW1iZXIgb2YgcGVvcGxlIHdobyBoYXZlIGFuIGV2ZW4gbnVtYmVyIG9mIGZyaWVuZHMgYXQgdGhlaXIgcGFydHkgaXMgYXMgbGFyZ2UgYXMgcG9zc2libGUsPFwvbGk+XHJcblx0PGxpPndyaXRlcyB0byB0aGUgc3RhbmRhcmQgb3V0cHV0IGEgbGlzdCBvZiBwZW9wbGUgd2hvIHNob3VsZCBiZSBpbnZpdGVkIHRvIHRoZSBmaXJzdCBwYXJ0eS48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+SW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIHN0YW5kYXJkIGlucHV0IHRoZXJlIGlzIG9uZSBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMjAwKSAtIGl0IGlzIHRoZSBudW1iZXIgb2YgaW5oYWJpdGFudHMgb2YgQnl0ZW90aWEuIFRoZSBpbmhhYml0YW50cyBhcmUgbnVtYmVyZWQgZnJvbSAxIHRvIE4uIEluIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyB0aGVyZSBhcmUgdGhlIGRlc2NyaXB0aW9ucyBvZiBzdWJzZXF1ZW50IHBlcnNvbnMmIzM5OyBhY3F1YWludGFuY2VzLiBBdCB0aGUgYmVnaW5uaW5nIG9mIHRoZSAoaSsxKSYjMzk7dGggbGluZSB0aGVyZSBpcyBhbiBpbnRlZ2VyIGw8c3ViPmk8XC9zdWI+ICgwICZsZTsgbDxzdWI+aTxcL3N1Yj4gJmxlOyBOLTEpIC0gdGhlIG51bWJlciBvZiBmcmllbmRzIG9mIHRoZSBpdGggaW5oYWJpdGFudC4gSXQgaXMgZm9sbG93ZWQgYnkgbDxzdWI+aTxcL3N1Yj4gcGFpcndpc2UgZGlzdGluY3QgbnVtYmVycyBvZiB0aGUgaSYjMzk7dGggaW5oYWJpdGFudCYjMzk7cyBmcmllbmRzLiBXZSBhc3N1bWUgdGhhdCBubyBpbmhhYml0YW50IGlzIGhlclwvaGlzIG93biBmcmllbmQuIEl0IGZvbGxvd3MgdGhhdCBlYWNoIGFjcXVhaW50YW5jZSBpcyB3cml0dGVuIHR3aWNlOiBpZiBBIGFuZCBCIGtub3cgZWFjaCBvdGhlciwgdGhlbiBCIGFwcGVhcnMgb24gQSYjMzk7cyBsaXN0IG9mIGZyaWVuZHMgYW5kIEEgYXBwZWFycyBvbiBCJiMzOTtzLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgb3V0cHV0IHlvdXIgcHJvZ3JhbW1lIHNob3VsZCB3cml0ZSBvbmUgaW50ZWdlciBNIC0gdGhlIG51bWJlciBvZiBwZW9wbGUgd2hvIGFyZSB0byBjb21lIHRvIHRoZSBmaXJzdCBwYXJ0eS4gSW4gdGhlIHNlY29uZCBsaW5lIHRoZSBNIG51bWJlcnMgb2YgdGhlc2UgcGVvcGxlIHNob3VsZCBiZSB3cml0dGVuLiBUaGUgcmVzdCBzaGFsbCBjb21lIHRvIHRoZSBzZWNvbmQgcGFydHkuPFwvcD5cclxuXHJcbjxwPlRoZXJlIGFyZSBtYW55IGNvcnJlY3QgZGl2aXNpb25zIGluIHRoaXMgdGFzayAtIHlvdXIgcHJvZ3JhbW1lIHNob3VsZCB3cml0ZSBhbnkgb25lIG9mIHRoZW0uPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZHdhemFkLWltZzIuZ2lmXCIgc3R5bGU9XCJoZWlnaHQ6MjMzcHg7IHdpZHRoOjIzNHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkluIHRoZSBhYm92ZSBleGFtcGxlIGV2ZXJ5b25lIHdpbGwgaGF2ZSBldmVuIG51bWJlciBvZiBmcmllbmRzIGF0IHRoZSBwYXJ0eS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Polish Olympiad in Informatics > POI 2004/2005 > Stage 3 3번

  • 문제를 번역한 사람: author6
  • 스페셜 저지를 만든 사람: koosaga