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

문제

N명의 사람들이 있다. 이들은 각자 다른 한 명의 이름이 적힌 쪽지를 받아서, 그 사람에게 몰래 선행을 베푼다. 이때 자기 자신의 이름을 받을 수는 없으며, 선행을 받은 사람은 누가 자신을 도와줬는지도 알 수 없다.

그런데 이런 마니또 활동을 하던 중 할 짓이 지지리도 없던 세종이는 여기서 "마니또 체인"이라는 개념을 발견했다! 세종이가 동우에게 선행을 베풀고, 동우가 재혁이에게 선행을 베풀고, 재혁이가 호용이에게 선행을 베풀고... 이렇게 하다 보면 언젠가 누군가는 처음 선행을 베푼 세종이에게 선행을 베풀게 되리라는 것이다. 이렇게 선행을 베푸는 연결 고리가 반드시 생긴다! 이 고리는 그냥 2명일 수도 있고, 아예 N명 모두가 포함될 수도 있다.

우리가 할 일은 N명의 사람들 사이에서 이러한 연결 고리가 몇 개나 발생하는지를 알아내는 것이다. 문제는 여러 개로 이루어져 있다.

입력

각 테스트 케이스의 첫 번째 줄에는 사람의 명수 N이 주어진다(3 <= N <=20). 만약 N = 0이면 입력의 끝을 의미하며 더 이상의 입력은 없다.

각 테스트 케이스의 두 번째 줄부터 N개의 줄에 거쳐 두 사람의 이름이 주어진다. 각 줄에 누가 누구에게 선행을 베푸는지가 주어진다. 첫 번째 이름과 두 번째 이름은 각각 해당 케이스 전체에 걸쳐 중복되지 않으며, 한 줄에 같은 이름이 두 번 등장하지 않는다. 이름의 길이는 10자를 넘지 않는다.

출력

각 테스트 케이스마다, 한 줄에 해당 케이스의 번호(1부터 시작)와 연결 고리의 개수를 공백을 두고 출력한다.

예제 입력 1

5
Andrew Sally
Chen Andrew
Ahmed Tess
Sally Chen
Tess Ahmed
0

예제 출력 1

1 2
W3sicHJvYmxlbV9pZCI6IjUxMDciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5YzhcdWIyYzhcdWI2MTAiLCJkZXNjcmlwdGlvbiI6IjxwPk5cdWJhODVcdWM3NTggXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViNGU0XHVjNzQwIFx1YWMwMVx1Yzc5MCBcdWIyZTRcdWI5NzggXHVkNTVjIFx1YmE4NVx1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3NzQgXHVjODAxXHVkNzhjIFx1Y2FiZFx1YzljMFx1Yjk3YyBcdWJjMWJcdWM1NDRcdWMxMWMsIFx1YWRmOCBcdWMwYWNcdWI3OGNcdWM1ZDBcdWFjOGMgXHViYWIwXHViNzk4IFx1YzEyMFx1ZDU4OVx1Yzc0NCBcdWJjYTBcdWQ0N2NcdWIyZTQuIFx1Yzc3NFx1YjU0YyBcdWM3OTBcdWFlMzAgXHVjNzkwXHVjMmUwXHVjNzU4IFx1Yzc3NFx1Yjk4NFx1Yzc0NCBcdWJjMWJcdWM3NDQgXHVjMjE4XHViMjk0IFx1YzVjNlx1YzczY1x1YmE3MCwgXHVjMTIwXHVkNTg5XHVjNzQ0IFx1YmMxYlx1Yzc0MCBcdWMwYWNcdWI3OGNcdWM3NDAgXHViMjA0XHVhYzAwIFx1Yzc5MFx1YzJlMFx1Yzc0NCBcdWIzYzRcdWM2NDBcdWM5MmNcdWIyOTRcdWM5YzBcdWIzYzQgXHVjNTRjIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjdmMFx1YjM3MCBcdWM3NzRcdWI3ZjAgXHViOWM4XHViMmM4XHViNjEwIFx1ZDY1Y1x1YjNkOVx1Yzc0NCBcdWQ1NThcdWIzNTggXHVjOTExIFx1ZDU2MCBcdWM5ZDNcdWM3NzQgXHVjOWMwXHVjOWMwXHViOWFjXHViM2M0IFx1YzVjNlx1YjM1OCBcdWMxMzhcdWM4ODVcdWM3NzRcdWIyOTQgXHVjNWVjXHVhZTMwXHVjMTFjICZxdW90O1x1YjljOFx1YjJjOFx1YjYxMCBcdWNjYjRcdWM3NzgmcXVvdDtcdWM3NzRcdWI3N2NcdWIyOTQgXHVhYzFjXHViMTUwXHVjNzQ0IFx1YmMxY1x1YWNhY1x1ZDU4OFx1YjJlNCEgXHVjMTM4XHVjODg1XHVjNzc0XHVhYzAwIFx1YjNkOVx1YzZiMFx1YzVkMFx1YWM4YyBcdWMxMjBcdWQ1ODlcdWM3NDQgXHViY2EwXHVkNDgwXHVhY2UwLCBcdWIzZDlcdWM2YjBcdWFjMDAgXHVjN2FjXHVkNjAxXHVjNzc0XHVjNWQwXHVhYzhjIFx1YzEyMFx1ZDU4OVx1Yzc0NCBcdWJjYTBcdWQ0ODBcdWFjZTAsIFx1YzdhY1x1ZDYwMVx1Yzc3NFx1YWMwMCBcdWQ2MzhcdWM2YTlcdWM3NzRcdWM1ZDBcdWFjOGMgXHVjMTIwXHVkNTg5XHVjNzQ0IFx1YmNhMFx1ZDQ4MFx1YWNlMC4uLiBcdWM3NzRcdWI4MDdcdWFjOGMgXHVkNTU4XHViMmU0IFx1YmNmNFx1YmE3NCBcdWM1YjhcdWM4MjBcdWFjMDAgXHViMjA0XHVhZDcwXHVhYzAwXHViMjk0IFx1Y2M5OFx1Yzc0YyBcdWMxMjBcdWQ1ODlcdWM3NDQgXHViY2EwXHVkNDdjIFx1YzEzOFx1Yzg4NVx1Yzc3NFx1YzVkMFx1YWM4YyBcdWMxMjBcdWQ1ODlcdWM3NDQgXHViY2EwXHVkNDgwXHVhYzhjIFx1YjQxOFx1YjlhY1x1Yjc3Y1x1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWMxMjBcdWQ1ODlcdWM3NDQgXHViY2EwXHVkNDc4XHViMjk0IFx1YzVmMFx1YWNiMCBcdWFjZTBcdWI5YWNcdWFjMDAgXHViYzE4XHViNGRjXHVjMmRjIFx1YzBkZFx1YWUzNFx1YjJlNCEgXHVjNzc0IFx1YWNlMFx1YjlhY1x1YjI5NCBcdWFkZjhcdWIwZTUgMlx1YmE4NVx1Yzc3YyBcdWMyMThcdWIzYzQgXHVjNzg4XHVhY2UwLCBcdWM1NDRcdWM2MDggTlx1YmE4NSBcdWJhYThcdWI0NTBcdWFjMDAgXHVkM2VjXHVkNTY4XHViNDIwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzZiMFx1YjlhY1x1YWMwMCBcdWQ1NjAgXHVjNzdjXHVjNzQwIE5cdWJhODVcdWM3NTggXHVjMGFjXHViNzhjXHViNGU0IFx1YzBhY1x1Yzc3NFx1YzVkMFx1YzExYyBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjNWYwXHVhY2IwIFx1YWNlMFx1YjlhY1x1YWMwMCBcdWJhODcgXHVhYzFjXHViMDk4IFx1YmMxY1x1YzBkZFx1ZDU1OFx1YjI5NFx1YzljMFx1Yjk3YyBcdWM1NGNcdWM1NDRcdWIwYjRcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWJiMzhcdWM4MWNcdWIyOTQgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzU4IFx1YmE4NVx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCgzICZsdDs9IE4gJmx0Oz0yMCkuIFx1YjljY1x1YzU3ZCBOID0gMFx1Yzc3NFx1YmE3NCBcdWM3ODVcdWI4MjVcdWM3NTggXHViMDVkXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YmE3MCBcdWIzNTQgXHVjNzc0XHVjMGMxXHVjNzU4IFx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3MFx1Y2NkMCBcdWI0NTAgXHVjMGFjXHViNzhjXHVjNzU4IFx1Yzc3NFx1Yjk4NFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSZuYnNwO1x1YzkwNFx1YzVkMCBcdWIyMDRcdWFjMDAgXHViMjA0XHVhZDZjXHVjNWQwXHVhYzhjIFx1YzEyMFx1ZDU4OVx1Yzc0NCBcdWJjYTBcdWQ0NzhcdWIyOTRcdWM5YzBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1Yzc3NFx1Yjk4NFx1YWNmYyBcdWI0NTAgXHViYzg4XHVjOWY4IFx1Yzc3NFx1Yjk4NFx1Yzc0MCBcdWFjMDFcdWFjMDEgXHVkNTc0XHViMmY5IFx1Y2YwMFx1Yzc3NFx1YzJhNCZuYnNwO1x1YzgwNFx1Y2NiNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVjOTExXHViY2Y1XHViNDE4XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3MCwgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWFjMTlcdWM3NDAgXHVjNzc0XHViOTg0XHVjNzc0IFx1YjQ1MCBcdWJjODggXHViNGYxXHVjN2E1XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVjNzc0XHViOTg0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAxMFx1Yzc5MFx1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0LCBcdWQ1NWMgXHVjOTA0XHVjNWQwJm5ic3A7XHVkNTc0XHViMmY5IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWJjODhcdWQ2MzgoMVx1YmQ4MFx1ZDEzMCBcdWMyZGNcdWM3OTEpXHVjNjQwIFx1YzVmMFx1YWNiMCBcdWFjZTBcdWI5YWNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWI0NTBcdWFjZTAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjUxMDciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTZWNyZXQgU2FudGEiLCJkZXNjcmlwdGlvbiI6IjxwPlNlY3JldCBTYW50YSB3b3JrcyBsaWtlIHRoaXMuIFRoZSBwZW9wbGUgaW4gYW4gb3JnYW5pc2F0aW9uIChlZyBhbiBvZmZpY2UpIGVhY2ggYnV5IG9uZSBDaHJpc3RtYXMgcHJlc2VudCBvZiBhIGdpdmVuIHZhbHVlIChlZyAkMTApLiBBbGwgdGhlIG5hbWVzIG9mIHRoZSBwZW9wbGUgcGFydGljaXBhdGluZyBhcmUgcHV0IGludG8gYSBoYXQsIGFuZCBlYWNoIHBlcnNvbiBkcmF3cyBvdXQgb25lIG5hbWUuIEEgcGVyc29uIGlzIG5vdCBhbGxvd2VkIHRvIGRyYXcgdGhlaXIgb3duIG5hbWUuIEVhY2ggcGVyc29uIHRoZW4gd3JpdGVzIG9uIHRoZWlyIGdpZnQgdGhlIG5hbWUgb2YgdGhlIHBlcnNvbiBkcmF3biBmcm9tIHRoZSBoYXQsIGFuZCB0aGUgcHJlc2VudHMgYXJlIHB1dCBpbiBhIHNhZmUgcGxhY2UgdW50aWwgdGhleSBhcmUgZ2l2ZW4gb3V0LiBUaGUgaWRlYSBpcyB0aGF0IG5vYm9keSBrbm93cyB3aG8gYm91Z2h0IHRoZSBwcmVzZW50IHRoYXQgdGhleSByZWNlaXZlLjxcL3A+XHJcblxyXG48cD5Tb21lYm9keSB3aXRoIHRvbyBtdWNoIHNwYXJlIHRpbWUgdGhvdWdodCBhYm91dCBsb29wcyBpbiB0aGUgZ2l2aW5nIGNoYWluISBJZiB5b3Ugc3RhcnQgd2l0aCBvbmUgcGVyc29uLCBtb3ZlIHRvIHRoZSBwZXJzb24gdG8gd2hvbSB0aGV5IGdhdmUgYSBwcmVzZW50LCB0aGVuIHRvIHRoZSBwZXJzb24gdG8gd2hvbSB0aGF0IHBlcnNvbiBnYXZlIGEgcHJlc2VudCwgeW91IHdvdWxkIGV2ZW50dWFsbHkgZW5kIHVwIGJhY2sgd2l0aCB0aGUgZmlyc3QgcGVyc29uICZuZGFzaDsgdGhhdCB3b3VsZCBiZSBhIGdpdmluZyBsb29wISBBIGdpdmluZyBsb29wIGNvdWxkIGJlIGp1c3QgMiBwZW9wbGUsIGlmIEEgZ2F2ZSB0byBCIGFuZCBCIGdhdmUgdG8gQS4gT24gdGhlIG90aGVyIGhhbmQsIHRoZXJlIGNvdWxkIGJlIGEgc2luZ2xlIGdpdmluZyBsb29wIGNvbnRhaW5pbmcgZXZlcnlib2R5LjxcL3A+XHJcblxyXG48cD5JbiB0aGlzIHByb2JsZW0sIHlvdSBoYXZlIHRvIHdyaXRlIGEgcHJvZ3JhbSB0byBjYWxjdWxhdGUgaG93IG1hbnkgZ2l2aW5nIGxvb3BzIHRoZXJlIGFyZSBpbiBhIG51bWJlciBvZiBTZWNyZXQgU2FudGEgc2NlbmFyaW9zLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgY29uc2lzdHMgb2YgYSBudW1iZXIgb2Ygc2NlbmFyaW9zLiBFYWNoIGJlZ2lucyB3aXRoIGEgc2luZ2xlIGludGVnZXIsIE4sIHRoZSBudW1iZXIgb2YgcGVvcGxlIHRha2luZyBwYXJ0ICgzICZsdDs9IE4gJmx0Oz0yMCkuIElucHV0IGVuZHMgd2l0aCBhIHNjZW5hcmlvIHdoZXJlIHRoZSBudW1iZXIgb2YgcGVvcGxlIHRha2luZyBwYXJ0IGlzIDAgJm5kYXNoOyB0aGlzIHNob3VsZCBub3QgYmUgcHJvY2Vzc2VkLjxcL3A+XHJcblxyXG48cD5JbiBlYWNoIHNjZW5hcmlvLCB0aGUgaW5pdGlhbCBpbnRlZ2VyIGlzIGZvbGxvd2VkIGJ5IE4gbGluZXMgb2YgZGF0YS4gQSBsaW5lIGNvbnNpc3RzIG9mIHRoZSBuYW1lIG9mIGEgcGVyc29uIGZvbGxvd2VkIGJ5IGEgc3BhY2UgZm9sbG93ZWQgYnkgdGhlIG5hbWUgb2YgYW5vdGhlciBwZXJzb24uIEluIHRoZSBOIGxpbmVzIG9mIGRhdGEgdGhlcmUgd2lsbCBiZSBOIGRpc3RpbmN0IG5hbWVzOyBlYWNoIG5hbWUgd2lsbCBhcHBlYXIgb25jZSBhcyB0aGUgZmlyc3QgbmFtZSBvbiBhIGxpbmUgYW5kIG9uY2UgYXMgdGhlIHNlY29uZCBuYW1lLiBObyBsaW5lIHdpbGwgY29udGFpbiB0aGUgc2FtZSBuYW1lIHR3aWNlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB3aWxsIGNvbnNpc3Qgb2YgdGhlIHNjZW5hcmlvIG51bWJlciBmb2xsb3dlZCBieSBhIHNwYWNlLCBmb2xsb3dlZCBieSB0aGUgbnVtYmVyIG9mIGdpdmluZyBsb29wcyBpbiB0aGF0IHNjZW5hcmlvLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > South Pacific > South Pacific Region > New Zealand Programming Contest > NZPC 2010 H번

  • 빠진 조건을 찾은 사람: jaehoo1
  • 문제를 번역한 사람: kks227