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

문제

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

이에 화가 난 주호는 공부에 대한 생각도 잊은채 위닝을 연습하기로 결심하였다. 하지만 수업시간에 컴퓨터로 직접 하는것이 힘들었기 때문에 바깥에서 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
W3sicHJvYmxlbV9pZCI6IjE5MTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3MDRcdWIyZGQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzViNFx1YzgxYyBcdWM3OTBcdWM3MjBcdWMyZGNcdWFjMDRcdWM1ZDAgXHVkNjNjXHVjNzkwIFx1YzcwNFx1YjJkZFx1Yzc0NCBcdWQ1NThcdWJhNzRcdWMxMWMgXHVjNzkwXHVjMmUwXHVjNzU4IFx1YzJlNFx1YjgyNVx1Yzc0NCBcdWM3OTBcdWI3OTFcdWQ1NThcdWIzNTggXHVjOGZjXHVkNjM4XHViMjk0IFx1YWMxNVx1Yzg3MFx1YWQ1MFx1ZDU1Y1x1ZDE0YyBcdWQzYjhcdWM1NDhcdWQ1NThcdWFjOGMgXHViYzg0XHVjMmE0XHViOTdjIFx1ZDBjMFx1YWNlMCBcdWI5ZDBcdWM1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YzVkMCBcdWQ2NTRcdWFjMDAgXHViMDljIFx1YzhmY1x1ZDYzOFx1YjI5NCBcdWFjZjVcdWJkODBcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzBkZFx1YWMwMVx1YjNjNCBcdWM3OGFcdWM3NDBcdWNjNDQgXHVjNzA0XHViMmRkXHVjNzQ0IFx1YzVmMFx1YzJiNVx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWFjYjBcdWMyZWNcdWQ1NThcdWM2MDBcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWMyMThcdWM1YzVcdWMyZGNcdWFjMDRcdWM1ZDAgXHVjZWY0XHVkNGU4XHVkMTMwXHViODVjIFx1YzljMVx1YzgxMSBcdWQ1NThcdWIyOTRcdWFjODNcdWM3NzQgXHVkNzk4XHViNGU0XHVjNWM4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWJjMTRcdWFlNjVcdWM1ZDBcdWMxMWMgTlx1YWMxY1x1Yzc1OCBcdWIzY2NcdWJhNjlcdWM3NzRcdWI4NWMgXHVjODA0XHViN2I1XHVjNzQ0IFx1YzEzOFx1YzZiMFx1YWUzMFx1Yjg1YyBcdWFjYjBcdWMyZWNcdWQ1NThcdWM2MDBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzhmY1x1ZDYzOFx1YjI5NCBcdWM1ZjBcdWFkNmNcdWQ1NWMgXHViMDVkXHVjNWQwIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YzU3ZFx1YzgxMFx1Yzc0MCBcdWQzMjhcdWMyYTRcdWI3N2NcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YWU2OFx1YjJlY1x1YzU1OFx1YjJlNC4gXHVhY2IwXHVhZDZkIFx1YzgwMVx1YzgwOFx1ZDU1OFx1YWM4YyBcdWIzY2NcdWJhNjlcdWM3NzRcdWI5N2MgXHViYzMwXHVjZTU4XHVkNTVjIFx1YjJlNFx1Yzc0YyBcdWQ2YThcdWM3MjhcdWM4MDFcdWM3M2NcdWI4NWMgXHVkMzI4XHVjMmE0XHVkNTU4XHViMjk0IFx1YmM5NVx1Yzc0NCBcdWM1ZjBcdWFkNmNcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTg4XHViMjk0XHViMzcwJmhlbGxpcDsuPFwvcD5cclxuXHJcbjxwPk5cdWFjMWNcdWM3NTggXHViM2NjXHViYTY5XHVjNzc0XHViNGU0XHVjNzc0IFx1Yzc4OFx1YWNlMCZuYnNwOyBcdWMwYzFcdWQ2MzhcdWFjMDRcdWM1ZDAgXHVkMzI4XHVjMmE0XHVhYzAwIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWMzMGRcdWI0ZTRcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWM5ODkgXHViYWE4XHViNGUwIFx1YzMwZFx1YjRlNCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHVkMzI4XHVjMmE0XHVhYzAwIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjODNcdWM3NzQgXHVjNTQ0XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4ZmNcdWQ2MzhcdWIyOTQgXHVjNzc0IFx1YjNjY1x1YmE2OVx1Yzc3NFx1YjRlNFx1Yzc0NCBcdWM4MDFcdWM4MDhcdWQ1NThcdWFjOGMgXHVhY2Y1XHVhY2E5IFx1YWRmOFx1YjhmOVx1YWNmYyBcdWMyMThcdWJlNDQgXHVhZGY4XHViOGY5XHVjNzU4IFx1YjQ1MCBcdWFkZjhcdWI4ZjlcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVhY2UwXHVjNzkwIFx1ZDU1Y1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1ZDMyOFx1YzJhNFx1YWMwMCBcdWQ2YThcdWM3MjhcdWM4MDFcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWMwXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExY1x1YjI5NCBcdWFjMDFcdWFjMDFcdWM3NTggXHViM2NjXHViYTY5XHVjNzc0XHViNGU0XHVjNWQwIFx1YjMwMFx1ZDU3NCwgXHVjNzkwXHVjMmUwXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWFkZjhcdWI4ZjlcdWM1ZDAgXHVjMThkXHVkNTc0IFx1Yzc4OFx1YzczY1x1YmE3NFx1YzExYyBcdWQzMjhcdWMyYTRcdWFjMDAgXHVhYzAwXHViMmE1XHVkNTVjIFx1YjNjY1x1YmE2OVx1Yzc3NFx1YjRlNFx1Yzc1OCBcdWMyMThcdWFjMDAgXHVjOWRkXHVjMjE4XHVhYzAwIFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YWNiMFx1YWQ2ZCBcdWM4ZmNcdWQ2MzhcdWM3NTggXHViYWE5XHVjODAxXHVjNzQwIFx1Yzc3NCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1Y2QxZCBcdWIzY2NcdWJhNjlcdWM3NzRcdWM3NTggXHVjMjJiXHVjNzkwXHVhYzAwIFx1Y2Q1Y1x1YjMwMCBcdWJhODcgXHVhYzFjXHVjNzc4XHVjOWMwIFx1YzU0Y1x1YzU0NFx1YjBiNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIzY2NcdWJhNjlcdWM3NzRcdWM3NTggXHVhYzFjXHVjMjE4IE4oMSAmbGU7IE4gJmxlOyAyMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBpKzFcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIGlcdWJjODhcdWM5ZjggXHViM2NjXHViYTY5XHVjNzc0XHVhYzAwIFx1ZDMyOFx1YzJhNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjNjY1x1YmE2OVx1Yzc3NFx1Yzc1OCBcdWFjMWNcdWMyMTggTDxzdWI+aTxcL3N1Yj5cdWFjMDAgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWFjMDFcdWFjMDFcdWM3NTggXHVjOTA0XHVjNWQwIEw8c3ViPmk8XC9zdWI+XHVhYzFjXHVjNzU4IFx1ZDMyOFx1YzJhNCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViM2NjXHViYTY5XHVjNzc0XHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWFjMDAgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0LiBcdWIyZTggXHVhYzAxXHVhYzAxXHVjNzU4IFx1YjNjY1x1YmE2OVx1Yzc3NFx1YjRlNFx1Yzc3NCBcdWM3OTBcdWMyZTBcdWM1ZDBcdWFjOGMgXHVkMzI4XHVjMmE0XHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWFjZTAsIEEgXHViM2NjXHViYTY5XHVjNzc0XHVhYzAwIEIgXHViM2NjXHViYTY5XHVjNzc0XHVjNzU4IFx1ZDMyOFx1YzJhNFx1YWMwMCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTRcdWJhNzQgQlx1YjNjNCBBXHVjNWQwXHVhYzhjIFx1ZDMyOFx1YzJhNFx1YWMwMCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTRcdWFjZTAgXHVkNTU4XHVjNzkwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWNmNVx1YWNhOVx1Yzc3NFx1YjA5OCBcdWMyMThcdWJlNDQgXHVjOTExIFx1ZDU1Y1x1Y2FiZCBcdWFkZjhcdWI4ZjlcdWM1ZDAgXHVjMThkXHVkNTVjIFx1YjNjY1x1YmE2OVx1Yzc3NFx1Yzc1OCBcdWFjMWNcdWMyMTggTVx1Yzc3NCBcdWNkOWNcdWI4MjVcdWI0MWNcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWFkZjggXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMCBcdWFkZjggXHVhZGY4XHViOGY5XHVjNWQwIFx1YzE4ZFx1ZDU1YyBcdWIzY2NcdWJhNjlcdWM3NzRcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Y2Q5Y1x1YjgyNVx1YjQxOFx1YzljMCBcdWM1NGFcdWM3NDAgXHVjMjJiXHVjNzkwXHViMjk0IFx1YmMxOFx1YjMwMFx1ZDNiOCBcdWFkZjhcdWI4ZjlcdWM1ZDAgXHVjMThkXHVkNTU4XHViMjk0IFx1YWM4M1x1YzczY1x1Yjg1YyBcdWQ1NWNcdWIyZTQuIFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzAgXHVkNTc0XHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjAgXHVhZGY4IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5Y2MgXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxOTEwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVHdvIFBhcnRpZXMiLCJkZXNjcmlwdGlvbiI6IjxwPktpbmcgQnl0ZWFzYXIgaGFzIGRlY2lkZWQgdG8gdGhyb3cgdHdvIGdyZWF0IHBhcnRpZXMgYW5kIHdhbnRzIHRvIGludml0ZSB0byB0aGVtIGV2ZXJ5IHNpbmdsZSBCeXRlb3RpYW4gaW5oYWJpdGFudC4gT2YgY291cnNlIGhlIHdhbnRzIHRvIGludml0ZSBlYWNoIG9mIHRoZW0gdG8gZXhhY3RseSBvbmUgb2YgdGhlIHBhcnRpZXMuIFRoZSBraW5nIGtub3dzIGZyb20gaGlzIG93biB2YXN0IGV4cGVyaWVuY2UgdGhhdCBhIHBlcnNvbiBpcyBoYXZpbmcgYSBnb29kIHRpbWUgd2hlbiB0aGVyZSBpcyBhbiBldmVuIG51bWJlciBvZiBoZXJcL2hpcyBmcmllbmRzIGF0IHRoZSBwYXJ0eS4gVGh1cyBoZSBoYXMgYXNrZWQgeW91IHRvIGRpdmlkZSB0aGUgY291bnRyeSYjMzk7cyBpbmhhYml0YW50cyBiZXR3ZWVuIHR3byBwYXJ0aWVzIGluIGEgd2F5IHRoYXQgYXMgbWFueSBwZW9wbGUgYXMgcG9zc2libGUgaGF2ZSBhbiBldmVuIG51bWJlciBvZiBmcmllbmRzIGF0IHRoZWlyIHBhcnR5LiBBIHRyaXZpYWwgZGl2aXNpb24sIGkuZS4gb25lIHRoYXQgbGVhdmVzIG9uZSBwYXJ0eSB3aXRoIG5vIGd1ZXN0cyBpbnZpdGVkLCBpcyBhbGxvd2VkLiBUaGUgYWNxdWFpbnRhbmNlc2hpcCBpcyBhIHN5bW1ldHJpYyByZWxhdGlvbiwgaS5lLiB3aGVuZXZlciBhIHBlcnNvbiBBIGtub3dzIHRoZSBwZXJzb24gQiwgdGhlIHBlcnNvbiBCIGFsc28ga25vd3MgdGhlIHBlcnNvbiBBLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW1tZSB0aGF0OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnJlYWRzIGZyb20gdGhlIHN0YW5kYXJkIGlucHV0IHRoZSBudW1iZXIgb2YgQnl0ZW90aWEmIzM5O3MgaW5oYWJpdGFudHMgYW5kIHRoZSBkZXNjcmlwdGlvbiBvZiB0aGVpciBhY3F1YWludGFuY2VzLDxcL2xpPlxyXG5cdDxsaT5zcGxpdHMgdGhlIGluaGFiaXRhbnRzIGludG8gdHdvIHBhcnRpZXMgaW4gc3VjaCB3YXkgdGhhdCB0aGUgbnVtYmVyIG9mIHBlb3BsZSB3aG8gaGF2ZSBhbiBldmVuIG51bWJlciBvZiBmcmllbmRzIGF0IHRoZWlyIHBhcnR5IGlzIGFzIGxhcmdlIGFzIHBvc3NpYmxlLDxcL2xpPlxyXG5cdDxsaT53cml0ZXMgdG8gdGhlIHN0YW5kYXJkIG91dHB1dCBhIGxpc3Qgb2YgcGVvcGxlIHdobyBzaG91bGQgYmUgaW52aXRlZCB0byB0aGUgZmlyc3QgcGFydHkuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPkluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBzdGFuZGFyZCBpbnB1dCB0aGVyZSBpcyBvbmUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDIwMCkgLSBpdCBpcyB0aGUgbnVtYmVyIG9mIGluaGFiaXRhbnRzIG9mIEJ5dGVvdGlhLiBUaGUgaW5oYWJpdGFudHMgYXJlIG51bWJlcmVkIGZyb20gMSB0byBOLiBJbiB0aGUgZm9sbG93aW5nIE4gbGluZXMgdGhlcmUgYXJlIHRoZSBkZXNjcmlwdGlvbnMgb2Ygc3Vic2VxdWVudCBwZXJzb25zJiMzOTsgYWNxdWFpbnRhbmNlcy4gQXQgdGhlIGJlZ2lubmluZyBvZiB0aGUgKGkrMSkmIzM5O3RoIGxpbmUgdGhlcmUgaXMgYW4gaW50ZWdlciBsPHN1Yj5pPFwvc3ViPiAoMCAmbGU7IGw8c3ViPmk8XC9zdWI+ICZsZTsgTi0xKSAtIHRoZSBudW1iZXIgb2YgZnJpZW5kcyBvZiB0aGUgaXRoIGluaGFiaXRhbnQuIEl0IGlzIGZvbGxvd2VkIGJ5IGw8c3ViPmk8XC9zdWI+IHBhaXJ3aXNlIGRpc3RpbmN0IG51bWJlcnMgb2YgdGhlIGkmIzM5O3RoIGluaGFiaXRhbnQmIzM5O3MgZnJpZW5kcy4gV2UgYXNzdW1lIHRoYXQgbm8gaW5oYWJpdGFudCBpcyBoZXJcL2hpcyBvd24gZnJpZW5kLiBJdCBmb2xsb3dzIHRoYXQgZWFjaCBhY3F1YWludGFuY2UgaXMgd3JpdHRlbiB0d2ljZTogaWYgQSBhbmQgQiBrbm93IGVhY2ggb3RoZXIsIHRoZW4gQiBhcHBlYXJzIG9uIEEmIzM5O3MgbGlzdCBvZiBmcmllbmRzIGFuZCBBIGFwcGVhcnMgb24gQiYjMzk7cy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIHN0YW5kYXJkIG91dHB1dCB5b3VyIHByb2dyYW1tZSBzaG91bGQgd3JpdGUgb25lIGludGVnZXIgTSAtIHRoZSBudW1iZXIgb2YgcGVvcGxlIHdobyBhcmUgdG8gY29tZSB0byB0aGUgZmlyc3QgcGFydHkuIEluIHRoZSBzZWNvbmQgbGluZSB0aGUgTSBudW1iZXJzIG9mIHRoZXNlIHBlb3BsZSBzaG91bGQgYmUgd3JpdHRlbi4gVGhlIHJlc3Qgc2hhbGwgY29tZSB0byB0aGUgc2Vjb25kIHBhcnR5LjxcL3A+XHJcblxyXG48cD5UaGVyZSBhcmUgbWFueSBjb3JyZWN0IGRpdmlzaW9ucyBpbiB0aGlzIHRhc2sgLSB5b3VyIHByb2dyYW1tZSBzaG91bGQgd3JpdGUgYW55IG9uZSBvZiB0aGVtLjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2R3YXphZC1pbWcyLmdpZlwiIHN0eWxlPVwiaGVpZ2h0OjIzM3B4OyB3aWR0aDoyMzRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5JbiB0aGUgYWJvdmUgZXhhbXBsZSBldmVyeW9uZSB3aWxsIGhhdmUgZXZlbiBudW1iZXIgb2YgZnJpZW5kcyBhdCB0aGUgcGFydHkuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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

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