시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 5 5 3 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+IiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIzY2NcdWJhNjlcdWM3NzRcdWM3NTggXHVhYzFjXHVjMjE4IE4oMSAmbHQ7PSBOICZsdDs9IDIwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIGkrMVx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgaVx1YmM4OFx1YzlmOCBcdWIzY2NcdWJhNjlcdWM3NzRcdWFjMDAgXHVkMzI4XHVjMmE0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViM2NjXHViYTY5XHVjNzc0XHVjNzU4IFx1YWMxY1x1YzIxOCBMaVx1YWMwMCBcdWI0ZTRcdWM1YjRcdWM2MjhcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWFkZjggXHViMmU0XHVjNzRjIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM5MDRcdWM1ZDAgTGlcdWFjMWNcdWM3NTggXHVkMzI4XHVjMmE0IFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWIzY2NcdWJhNjlcdWM3NzRcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWI0ZTRcdWM1YjRcdWM2MjhcdWIyZTQuIFx1YjJlOCBcdWFjMDFcdWFjMDFcdWM3NTggXHViM2NjXHViYTY5XHVjNzc0XHViNGU0XHVjNzc0IFx1Yzc5MFx1YzJlMFx1YzVkMFx1YWM4YyBcdWQzMjhcdWMyYTRcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YWNlMCwgQSBcdWIzY2NcdWJhNjlcdWM3NzRcdWFjMDAgQiBcdWIzY2NcdWJhNjlcdWM3NzRcdWM3NTggXHVkMzI4XHVjMmE0XHVhYzAwIFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNFx1YmE3NCBCXHViM2M0IEFcdWM1ZDBcdWFjOGMgXHVkMzI4XHVjMmE0XHVhYzAwIFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAuPFwvcD4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjZjVcdWFjYTlcdWM3NzRcdWIwOTggXHVjMjE4XHViZTQ0IFx1YzkxMSBcdWQ1NWNcdWNhYmQgXHVhZGY4XHViOGY5XHVjNWQwIFx1YzE4ZFx1ZDU1YyBcdWIzY2NcdWJhNjlcdWM3NzRcdWM3NTggXHVhYzFjXHVjMjE4IE1cdWM3NzQgXHVjZDljXHViODI1XHViNDFjXHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDAgXHVhZGY4IFx1YWRmOFx1YjhmOVx1YzVkMCBcdWMxOGRcdWQ1NWMgXHViM2NjXHViYTY5XHVjNzc0XHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWNkOWNcdWI4MjVcdWI0MThcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWJjMThcdWIzMDBcdWQzYjggXHVhZGY4XHViOGY5XHVjNWQwIFx1YzE4ZFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3M2NcdWI4NWMgXHVkNTVjXHViMmU0LiBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwIFx1ZDU3NFx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwIFx1YWRmOCBcdWM5MTEgXHVkNTU4XHViMDk4XHViOWNjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxOTEwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVHdvIFBhcnRpZXMiLCJkZXNjcmlwdGlvbiI6IjxwPktpbmcgQnl0ZWFzYXIgaGFzIGRlY2lkZWQgdG8gdGhyb3cgdHdvIGdyZWF0IHBhcnRpZXMgYW5kIHdhbnRzIHRvIGludml0ZSB0byB0aGVtIGV2ZXJ5IHNpbmdsZSBCeXRlb3RpYW4gaW5oYWJpdGFudC4gT2YgY291cnNlIGhlIHdhbnRzIHRvIGludml0ZSBlYWNoIG9mIHRoZW0gdG8gZXhhY3RseSBvbmUgb2YgdGhlIHBhcnRpZXMuIFRoZSBraW5nIGtub3dzIGZyb20gaGlzIG93biB2YXN0IGV4cGVyaWVuY2UgdGhhdCBhIHBlcnNvbiBpcyBoYXZpbmcgYSBnb29kIHRpbWUgd2hlbiB0aGVyZSBpcyBhbiBldmVuIG51bWJlciBvZiBoZXJcL2hpcyBmcmllbmRzIGF0IHRoZSBwYXJ0eS4gVGh1cyBoZSBoYXMgYXNrZWQgeW91IHRvIGRpdmlkZSB0aGUgY291bnRyeSYjMzk7cyBpbmhhYml0YW50cyBiZXR3ZWVuIHR3byBwYXJ0aWVzIGluIGEgd2F5IHRoYXQgYXMgbWFueSBwZW9wbGUgYXMgcG9zc2libGUgaGF2ZSBhbiBldmVuIG51bWJlciBvZiBmcmllbmRzIGF0IHRoZWlyIHBhcnR5LiBBIHRyaXZpYWwgZGl2aXNpb24sIGkuZS4gb25lIHRoYXQgbGVhdmVzIG9uZSBwYXJ0eSB3aXRoIG5vIGd1ZXN0cyBpbnZpdGVkLCBpcyBhbGxvd2VkLiBUaGUgYWNxdWFpbnRhbmNlc2hpcCBpcyBhIHN5bW1ldHJpYyByZWxhdGlvbiwgaS5lLiB3aGVuZXZlciBhIHBlcnNvbiBBIGtub3dzIHRoZSBwZXJzb24gQiwgdGhlIHBlcnNvbiBCIGFsc28ga25vd3MgdGhlIHBlcnNvbiBBLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW1tZSB0aGF0OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnJlYWRzIGZyb20gdGhlIHN0YW5kYXJkIGlucHV0IHRoZSBudW1iZXIgb2YgQnl0ZW90aWEmIzM5O3MgaW5oYWJpdGFudHMgYW5kIHRoZSBkZXNjcmlwdGlvbiBvZiB0aGVpciBhY3F1YWludGFuY2VzLDxcL2xpPlxyXG5cdDxsaT5zcGxpdHMgdGhlIGluaGFiaXRhbnRzIGludG8gdHdvIHBhcnRpZXMgaW4gc3VjaCB3YXkgdGhhdCB0aGUgbnVtYmVyIG9mIHBlb3BsZSB3aG8gaGF2ZSBhbiBldmVuIG51bWJlciBvZiBmcmllbmRzIGF0IHRoZWlyIHBhcnR5IGlzIGFzIGxhcmdlIGFzIHBvc3NpYmxlLDxcL2xpPlxyXG5cdDxsaT53cml0ZXMgdG8gdGhlIHN0YW5kYXJkIG91dHB1dCBhIGxpc3Qgb2YgcGVvcGxlIHdobyBzaG91bGQgYmUgaW52aXRlZCB0byB0aGUgZmlyc3QgcGFydHkuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPkluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBzdGFuZGFyZCBpbnB1dCB0aGVyZSBpcyBvbmUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDIwMCkgLSBpdCBpcyB0aGUgbnVtYmVyIG9mIGluaGFiaXRhbnRzIG9mIEJ5dGVvdGlhLiBUaGUgaW5oYWJpdGFudHMgYXJlIG51bWJlcmVkIGZyb20gMSB0byBOLiBJbiB0aGUgZm9sbG93aW5nIE4gbGluZXMgdGhlcmUgYXJlIHRoZSBkZXNjcmlwdGlvbnMgb2Ygc3Vic2VxdWVudCBwZXJzb25zJiMzOTsgYWNxdWFpbnRhbmNlcy4gQXQgdGhlIGJlZ2lubmluZyBvZiB0aGUgKGkrMSkmIzM5O3RoIGxpbmUgdGhlcmUgaXMgYW4gaW50ZWdlciBsPHN1Yj5pPFwvc3ViPiAoMCAmbGU7IGw8c3ViPmk8XC9zdWI+ICZsZTsgTi0xKSAtIHRoZSBudW1iZXIgb2YgZnJpZW5kcyBvZiB0aGUgaXRoIGluaGFiaXRhbnQuIEl0IGlzIGZvbGxvd2VkIGJ5IGw8c3ViPmk8XC9zdWI+IHBhaXJ3aXNlIGRpc3RpbmN0IG51bWJlcnMgb2YgdGhlIGkmIzM5O3RoIGluaGFiaXRhbnQmIzM5O3MgZnJpZW5kcy4gV2UgYXNzdW1lIHRoYXQgbm8gaW5oYWJpdGFudCBpcyBoZXJcL2hpcyBvd24gZnJpZW5kLiBJdCBmb2xsb3dzIHRoYXQgZWFjaCBhY3F1YWludGFuY2UgaXMgd3JpdHRlbiB0d2ljZTogaWYgQSBhbmQgQiBrbm93IGVhY2ggb3RoZXIsIHRoZW4gQiBhcHBlYXJzIG9uIEEmIzM5O3MgbGlzdCBvZiBmcmllbmRzIGFuZCBBIGFwcGVhcnMgb24gQiYjMzk7cy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIHN0YW5kYXJkIG91dHB1dCB5b3VyIHByb2dyYW1tZSBzaG91bGQgd3JpdGUgb25lIGludGVnZXIgTSAtIHRoZSBudW1iZXIgb2YgcGVvcGxlIHdobyBhcmUgdG8gY29tZSB0byB0aGUgZmlyc3QgcGFydHkuIEluIHRoZSBzZWNvbmQgbGluZSB0aGUgTSBudW1iZXJzIG9mIHRoZXNlIHBlb3BsZSBzaG91bGQgYmUgd3JpdHRlbi4gVGhlIHJlc3Qgc2hhbGwgY29tZSB0byB0aGUgc2Vjb25kIHBhcnR5LjxcL3A+XHJcblxyXG48cD5UaGVyZSBhcmUgbWFueSBjb3JyZWN0IGRpdmlzaW9ucyBpbiB0aGlzIHRhc2sgLSB5b3VyIHByb2dyYW1tZSBzaG91bGQgd3JpdGUgYW55IG9uZSBvZiB0aGVtLjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2R3YXphZC1pbWcyLmdpZlwiIHN0eWxlPVwiaGVpZ2h0OjIzM3B4OyB3aWR0aDoyMzRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5JbiB0aGUgYWJvdmUgZXhhbXBsZSBldmVyeW9uZSB3aWxsIGhhdmUgZXZlbiBudW1iZXIgb2YgZnJpZW5kcyBhdCB0aGUgcGFydHkuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

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