시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 70 42 36 59.016%

문제

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

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

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

입력

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

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

출력

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

예제 입력 1

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

예제 출력 1

1 2
W3sicHJvYmxlbV9pZCI6IjUxMDciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5YzhcdWIyYzhcdWI2MTAiLCJkZXNjcmlwdGlvbiI6IjxwPk5cdWJhODVcdWM3NTggXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViNGU0XHVjNzQwIFx1YWMwMVx1Yzc5MCBcdWIyZTRcdWI5NzggXHVkNTVjIFx1YmE4NVx1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3NzQgXHVjODAxXHVkNzhjIFx1Y2FiZFx1YzljMFx1Yjk3YyBcdWJjMWJcdWM1NDRcdWMxMWMsIFx1YWRmOCBcdWMwYWNcdWI3OGNcdWM1ZDBcdWFjOGMgXHViYWIwXHViNzk4IFx1YzEyMFx1ZDU4OVx1Yzc0NCBcdWJjYTBcdWQ0N2NcdWIyZTQuIFx1Yzc3NFx1YjU0YyBcdWM3OTBcdWFlMzAgXHVjNzkwXHVjMmUwXHVjNzU4IFx1Yzc3NFx1Yjk4NFx1Yzc0NCBcdWJjMWJcdWM3NDQgXHVjMjE4XHViMjk0IFx1YzVjNlx1YzczY1x1YmE3MCwgXHVjMTIwXHVkNTg5XHVjNzQ0IFx1YmMxYlx1Yzc0MCBcdWMwYWNcdWI3OGNcdWM3NDAgXHViMjA0XHVhYzAwIFx1Yzc5MFx1YzJlMFx1Yzc0NCBcdWIzYzRcdWM2NDBcdWM5MmNcdWIyOTRcdWM5YzBcdWIzYzQgXHVjNTRjIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjdmMFx1YjM3MCBcdWM3NzRcdWI3ZjAgXHViOWM4XHViMmM4XHViNjEwIFx1ZDY1Y1x1YjNkOVx1Yzc0NCBcdWQ1NThcdWIzNTggXHVjOTExIFx1ZDU2MCBcdWM5ZDNcdWM3NzQgXHVjOWMwXHVjOWMwXHViOWFjXHViM2M0IFx1YzVjNlx1YjM1OCBcdWMxMzhcdWM4ODVcdWM3NzRcdWIyOTQgXHVjNWVjXHVhZTMwXHVjMTFjICZxdW90O1x1YjljOFx1YjJjOFx1YjYxMCBcdWNjYjRcdWM3NzgmcXVvdDtcdWM3NzRcdWI3N2NcdWIyOTQgXHVhYzFjXHViMTUwXHVjNzQ0IFx1YmMxY1x1YWNhY1x1ZDU4OFx1YjJlNCEgXHVjMTM4XHVjODg1XHVjNzc0XHVhYzAwIFx1YjNkOVx1YzZiMFx1YzVkMFx1YWM4YyBcdWMxMjBcdWQ1ODlcdWM3NDQgXHViY2EwXHVkNDgwXHVhY2UwLCBcdWIzZDlcdWM2YjBcdWFjMDAgXHVjN2FjXHVkNjAxXHVjNzc0XHVjNWQwXHVhYzhjIFx1YzEyMFx1ZDU4OVx1Yzc0NCBcdWJjYTBcdWQ0ODBcdWFjZTAsIFx1YzdhY1x1ZDYwMVx1Yzc3NFx1YWMwMCBcdWQ2MzhcdWM2YTlcdWM3NzRcdWM1ZDBcdWFjOGMgXHVjMTIwXHVkNTg5XHVjNzQ0IFx1YmNhMFx1ZDQ4MFx1YWNlMC4uLiBcdWM3NzRcdWI4MDdcdWFjOGMgXHVkNTU4XHViMmU0IFx1YmNmNFx1YmE3NCBcdWM1YjhcdWM4MjBcdWFjMDAgXHViMjA0XHVhZDcwXHVhYzAwXHViMjk0IFx1Y2M5OFx1Yzc0YyBcdWMxMjBcdWQ1ODlcdWM3NDQgXHViY2EwXHVkNDdjIFx1YzEzOFx1Yzg4NVx1Yzc3NFx1YzVkMFx1YWM4YyBcdWMxMjBcdWQ1ODlcdWM3NDQgXHViY2EwXHVkNDgwXHVhYzhjIFx1YjQxOFx1YjlhY1x1Yjc3Y1x1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWMxMjBcdWQ1ODlcdWM3NDQgXHViY2EwXHVkNDc4XHViMjk0IFx1YzVmMFx1YWNiMCBcdWFjZTBcdWI5YWNcdWFjMDAgXHViYzE4XHViNGRjXHVjMmRjIFx1YzBkZFx1YWUzNFx1YjJlNCEgXHVjNzc0IFx1YWNlMFx1YjlhY1x1YjI5NCBcdWFkZjhcdWIwZTUgMlx1YmE4NVx1Yzc3YyBcdWMyMThcdWIzYzQgXHVjNzg4XHVhY2UwLCBcdWM1NDRcdWM2MDggTlx1YmE4NSBcdWJhYThcdWI0NTBcdWFjMDAgXHVkM2VjXHVkNTY4XHViNDIwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzZiMFx1YjlhY1x1YWMwMCBcdWQ1NjAgXHVjNzdjXHVjNzQwIE5cdWJhODVcdWM3NTggXHVjMGFjXHViNzhjXHViNGU0IFx1YzBhY1x1Yzc3NFx1YzVkMFx1YzExYyBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjNWYwXHVhY2IwIFx1YWNlMFx1YjlhY1x1YWMwMCBcdWJhODcgXHVhYzFjXHViMDk4IFx1YmMxY1x1YzBkZFx1ZDU1OFx1YjI5NFx1YzljMFx1Yjk3YyBcdWM1NGNcdWM1NDRcdWIwYjRcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWJiMzhcdWM4MWNcdWIyOTQgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzU4IFx1YmE4NVx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCgzICZsdDs9IE4gJmx0Oz0yMCkuIFx1YjljY1x1YzU3ZCBOID0gMFx1Yzc3NFx1YmE3NCBcdWM3ODVcdWI4MjVcdWM3NTggXHViMDVkXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YmE3MCBcdWIzNTQgXHVjNzc0XHVjMGMxXHVjNzU4IFx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3MFx1Y2NkMCBcdWI0NTAgXHVjMGFjXHViNzhjXHVjNzU4IFx1Yzc3NFx1Yjk4NFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSZuYnNwO1x1YzkwNFx1YzVkMCBcdWIyMDRcdWFjMDAgXHViMjA0XHVhZDZjXHVjNWQwXHVhYzhjIFx1YzEyMFx1ZDU4OVx1Yzc0NCBcdWJjYTBcdWQ0NzhcdWIyOTRcdWM5YzBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1Yzc3NFx1Yjk4NFx1YWNmYyBcdWI0NTAgXHViYzg4XHVjOWY4IFx1Yzc3NFx1Yjk4NFx1Yzc0MCBcdWFjMDFcdWFjMDEgXHVkNTc0XHViMmY5IFx1Y2YwMFx1Yzc3NFx1YzJhNCZuYnNwO1x1YzgwNFx1Y2NiNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVjOTExXHViY2Y1XHViNDE4XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3MCwgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWFjMTlcdWM3NDAgXHVjNzc0XHViOTg0XHVjNzc0IFx1YjQ1MCBcdWJjODggXHViNGYxXHVjN2E1XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCwgXHVkNTVjIFx1YzkwNFx1YzVkMCZuYnNwO1x1ZDU3NFx1YjJmOSBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHViYzg4XHVkNjM4KDFcdWJkODBcdWQxMzAgXHVjMmRjXHVjNzkxKVx1YzY0MCBcdWM1ZjBcdWFjYjAgXHVhY2UwXHViOWFjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFjZjVcdWJjMzFcdWM3NDQgXHViNDUwXHVhY2UwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1MTA3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU2VjcmV0IFNhbnRhIiwiZGVzY3JpcHRpb24iOiI8cD5TZWNyZXQgU2FudGEgd29ya3MgbGlrZSB0aGlzLiBUaGUgcGVvcGxlIGluIGFuIG9yZ2FuaXNhdGlvbiAoZWcgYW4gb2ZmaWNlKSBlYWNoIGJ1eSBvbmUgQ2hyaXN0bWFzIHByZXNlbnQgb2YgYSBnaXZlbiB2YWx1ZSAoZWcgJDEwKS4gQWxsIHRoZSBuYW1lcyBvZiB0aGUgcGVvcGxlIHBhcnRpY2lwYXRpbmcgYXJlIHB1dCBpbnRvIGEgaGF0LCBhbmQgZWFjaCBwZXJzb24gZHJhd3Mgb3V0IG9uZSBuYW1lLiBBIHBlcnNvbiBpcyBub3QgYWxsb3dlZCB0byBkcmF3IHRoZWlyIG93biBuYW1lLiBFYWNoIHBlcnNvbiB0aGVuIHdyaXRlcyBvbiB0aGVpciBnaWZ0IHRoZSBuYW1lIG9mIHRoZSBwZXJzb24gZHJhd24gZnJvbSB0aGUgaGF0LCBhbmQgdGhlIHByZXNlbnRzIGFyZSBwdXQgaW4gYSBzYWZlIHBsYWNlIHVudGlsIHRoZXkgYXJlIGdpdmVuIG91dC4gVGhlIGlkZWEgaXMgdGhhdCBub2JvZHkga25vd3Mgd2hvIGJvdWdodCB0aGUgcHJlc2VudCB0aGF0IHRoZXkgcmVjZWl2ZS48XC9wPlxyXG5cclxuPHA+U29tZWJvZHkgd2l0aCB0b28gbXVjaCBzcGFyZSB0aW1lIHRob3VnaHQgYWJvdXQgbG9vcHMgaW4gdGhlIGdpdmluZyBjaGFpbiEgSWYgeW91IHN0YXJ0IHdpdGggb25lIHBlcnNvbiwgbW92ZSB0byB0aGUgcGVyc29uIHRvIHdob20gdGhleSBnYXZlIGEgcHJlc2VudCwgdGhlbiB0byB0aGUgcGVyc29uIHRvIHdob20gdGhhdCBwZXJzb24gZ2F2ZSBhIHByZXNlbnQsIHlvdSB3b3VsZCBldmVudHVhbGx5IGVuZCB1cCBiYWNrIHdpdGggdGhlIGZpcnN0IHBlcnNvbiAmbmRhc2g7IHRoYXQgd291bGQgYmUgYSBnaXZpbmcgbG9vcCEgQSBnaXZpbmcgbG9vcCBjb3VsZCBiZSBqdXN0IDIgcGVvcGxlLCBpZiBBIGdhdmUgdG8gQiBhbmQgQiBnYXZlIHRvIEEuIE9uIHRoZSBvdGhlciBoYW5kLCB0aGVyZSBjb3VsZCBiZSBhIHNpbmdsZSBnaXZpbmcgbG9vcCBjb250YWluaW5nIGV2ZXJ5Ym9keS48XC9wPlxyXG5cclxuPHA+SW4gdGhpcyBwcm9ibGVtLCB5b3UgaGF2ZSB0byB3cml0ZSBhIHByb2dyYW0gdG8gY2FsY3VsYXRlIGhvdyBtYW55IGdpdmluZyBsb29wcyB0aGVyZSBhcmUgaW4gYSBudW1iZXIgb2YgU2VjcmV0IFNhbnRhIHNjZW5hcmlvcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IGNvbnNpc3RzIG9mIGEgbnVtYmVyIG9mIHNjZW5hcmlvcy4gRWFjaCBiZWdpbnMgd2l0aCBhIHNpbmdsZSBpbnRlZ2VyLCBOLCB0aGUgbnVtYmVyIG9mIHBlb3BsZSB0YWtpbmcgcGFydCAoMyAmbHQ7PSBOICZsdDs9MjApLiBJbnB1dCBlbmRzIHdpdGggYSBzY2VuYXJpbyB3aGVyZSB0aGUgbnVtYmVyIG9mIHBlb3BsZSB0YWtpbmcgcGFydCBpcyAwICZuZGFzaDsgdGhpcyBzaG91bGQgbm90IGJlIHByb2Nlc3NlZC48XC9wPlxyXG5cclxuPHA+SW4gZWFjaCBzY2VuYXJpbywgdGhlIGluaXRpYWwgaW50ZWdlciBpcyBmb2xsb3dlZCBieSBOIGxpbmVzIG9mIGRhdGEuIEEgbGluZSBjb25zaXN0cyBvZiB0aGUgbmFtZSBvZiBhIHBlcnNvbiBmb2xsb3dlZCBieSBhIHNwYWNlIGZvbGxvd2VkIGJ5IHRoZSBuYW1lIG9mIGFub3RoZXIgcGVyc29uLiBJbiB0aGUgTiBsaW5lcyBvZiBkYXRhIHRoZXJlIHdpbGwgYmUgTiBkaXN0aW5jdCBuYW1lczsgZWFjaCBuYW1lIHdpbGwgYXBwZWFyIG9uY2UgYXMgdGhlIGZpcnN0IG5hbWUgb24gYSBsaW5lIGFuZCBvbmNlIGFzIHRoZSBzZWNvbmQgbmFtZS4gTm8gbGluZSB3aWxsIGNvbnRhaW4gdGhlIHNhbWUgbmFtZSB0d2ljZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgd2lsbCBjb25zaXN0IG9mIHRoZSBzY2VuYXJpbyBudW1iZXIgZm9sbG93ZWQgYnkgYSBzcGFjZSwgZm9sbG93ZWQgYnkgdGhlIG51bWJlciBvZiBnaXZpbmcgbG9vcHMgaW4gdGhhdCBzY2VuYXJpby48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=