시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 4580 1342 670 23.860%

문제

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.

어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 가입한 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

출력

친구 관계가 생길 때마다, 가입한 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

예제 입력 1

2
3
Fred Barney
Barney Betty
Betty Wilma
3
Fred Barney
Betty Wilma
Barney Betty

예제 출력 1

2
3
4
2
2
4
W3sicHJvYmxlbV9pZCI6IjQxOTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNlNWNcdWFkNmMgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWJiZmNcdWQ2MDFcdWM3NzRcdWIyOTQgXHVjMThjXHVjMTVjIFx1YjEyNFx1ZDJiOFx1YzZjY1x1ZDA2YyZuYnNwO1x1YzBhY1x1Yzc3NFx1ZDJiOFx1YzVkMFx1YzExYyBcdWNlNWNcdWFkNmNcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHVjZTVjXHVhZDZjXHVjNzc0XHViMmU0LiBcdWM2YjBcdWQ0NWNcdWI5N2MgXHViYWE4XHVjNzNjXHViMjk0IFx1Y2RlOFx1YmJmOFx1YWMwMCBcdWM3ODhcdWI0ZWZcdWM3NzQsIFx1YmJmY1x1ZDYwMVx1Yzc3NFx1YjI5NCBcdWMxOGNcdWMxNWMgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjJm5ic3A7XHVjMGFjXHVjNzc0XHVkMmI4XHVjNWQwXHVjMTFjIFx1Y2U1Y1x1YWQ2Y1x1Yjk3YyBcdWJhYThcdWM3M2NcdWIyOTQgXHVhYzgzXHVjNzc0IFx1Y2RlOFx1YmJmOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViNWE0IFx1YzBhY1x1Yzc3NFx1ZDJiOFx1Yzc1OCBcdWNlNWNcdWFkNmMgXHVhZDAwXHVhY2M0XHVhYzAwIFx1YzBkZFx1YWUzNCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhYzAwXHVjNzg1XHVkNTVjIFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NTggXHVjZTVjXHVhZDZjIFx1YjEyNFx1ZDJiOFx1YzZjY1x1ZDA2Y1x1YzVkMCBcdWJhODcgXHViYTg1XHVjNzc0IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHVjZTVjXHVhZDZjIFx1YjEyNFx1ZDJiOFx1YzZjY1x1ZDA2Y1x1Yjc4MCBcdWNlNWNcdWFkNmMgXHVhZDAwXHVhY2M0XHViOWNjXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzBhY1x1Yzc3NFx1Yjk3YyBcdWI5ZDBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNlNWNcdWFkNmMgXHVhZDAwXHVhY2M0XHVjNzU4IFx1YzIxOCBGXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjNzc0IFx1YWMxMlx1Yzc0MCAxMDAsMDAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBGXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNlNWNcdWFkNmMgXHVhZDAwXHVhY2M0XHVhYzAwIFx1YzBkZFx1YWUzNCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWNlNWNcdWFkNmMgXHVhZDAwXHVhY2M0XHViMjk0IFx1YjQ1MCBcdWMwYWNcdWM2YTlcdWM3OTBcdWM3NTggXHVjNTQ0XHVjNzc0XHViNTE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWIzMDBcdWJiMzhcdWM3OTAgXHViNjEwXHViMjk0IFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVhZTM4XHVjNzc0IDIwIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZTVjXHVhZDZjIFx1YWQwMFx1YWNjNFx1YWMwMCBcdWMwZGRcdWFlMzggXHViNTRjXHViOWM4XHViMmU0LCBcdWFjMDBcdWM3ODVcdWQ1NWMgXHViNDUwIFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWNlNWNcdWFkNmMgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjXHVjNWQwIFx1YmE4NyBcdWJhODVcdWM3NzQgXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQxOTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJWaXJ0dWFsIEZyaWVuZHMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZXNlIGRheXMsIHlvdSBjYW4gZG8gYWxsIHNvcnRzIG9mIHRoaW5ncyBvbmxpbmUuIEZvciBleGFtcGxlLCB5b3UgY2FuIHVzZSB2YXJpb3VzIHdlYnNpdGVzIHRvIG1ha2UgdmlydHVhbCBmcmllbmRzLiBGb3Igc29tZSBwZW9wbGUsIGdyb3dpbmcgdGhlaXIgc29jaWFsIG5ldHdvcmsgKHRoZWlyIGZyaWVuZHMsIHRoZWlyIGZyaWVuZHMmIzM5OyBmcmllbmRzLCB0aGVpciBmcmllbmRzJiMzOTsgZnJpZW5kcyYjMzk7IGZyaWVuZHMsIGFuZCBzbyBvbiksIGhhcyBiZWNvbWUgYW4gYWRkaWN0aXZlIGhvYmJ5LiBKdXN0IGFzIHNvbWUgcGVvcGxlIGNvbGxlY3Qgc3RhbXBzLCBvdGhlciBwZW9wbGUgY29sbGVjdCB2aXJ0dWFsIGZyaWVuZHMuPFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byBvYnNlcnZlIHRoZSBpbnRlcmFjdGlvbnMgb24gc3VjaCBhIHdlYnNpdGUgYW5kIGtlZXAgdHJhY2sgb2YgdGhlIHNpemUgb2YgZWFjaCBwZXJzb24mIzM5O3MgbmV0d29yay48XC9wPlxyXG5cclxuPHA+QXNzdW1lIHRoYXQgZXZlcnkgZnJpZW5kc2hpcCBpcyBtdXR1YWwuIElmIEZyZWQgaXMgQmFybmV5JiMzOTtzIGZyaWVuZCwgdGhlbiBCYXJuZXkgaXMgYWxzbyBGcmVkJiMzOTtzIGZyaWVuZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIG9uZSBpbnRlZ2VyIHNwZWNpZnlpbmcgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIHRvIGZvbGxvdy4gRWFjaCB0ZXN0IGNhc2UgYmVnaW5zIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciBGLCB0aGUgbnVtYmVyIG9mIGZyaWVuZHNoaXBzIGZvcm1lZCwgd2hpY2ggaXMgbm8gbW9yZSB0aGFuIDEwMCAwMDAuIEVhY2ggb2YgdGhlIGZvbGxvd2luZyBGIGxpbmVzIGNvbnRhaW5zIHRoZSBuYW1lcyBvZiB0d28gcGVvcGxlIHdobyBoYXZlIGp1c3QgYmVjb21lIGZyaWVuZHMsIHNlcGFyYXRlZCBieSBhIHNwYWNlLiBBIG5hbWUgaXMgYSBzdHJpbmcgb2YgMSB0byAyMCBsZXR0ZXJzICh1cHBlcmNhc2Ugb3IgbG93ZXJjYXNlKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5XaGVuZXZlciBhIGZyaWVuZHNoaXAgaXMgZm9ybWVkLCBwcmludCBhIGxpbmUgY29udGFpbmluZyBvbmUgaW50ZWdlciwgdGhlIG51bWJlciBvZiBwZW9wbGUgaW4gdGhlIHNvY2lhbCBuZXR3b3JrIG9mIHRoZSB0d28gcGVvcGxlIHdobyBoYXZlIGp1c3QgYmVjb21lIGZyaWVuZHMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d