시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 228 95 63 41.722%

문제

진욱이는 새로운 소셜 네트워킹 회사를 만들기로 결심했다. 하지만 기존의 페이스북 이나 트위터 같이 인기있는 소셜 네트워크 서비스는 이미 수십억의 사용자를 가지고 있고, 진욱이는 이들과 경쟁에서 승리하는 유일한 방법은 다른 소셜 네트워크가 가지고 있지 않은 새로운 기능을 포함하는 것이라 생각했다.

진욱이는 광고주에게 값싼 방법으로 광고비를 청구할 방법을 생각해냈다. 광고주는 어떤 사용자의 담벼락에 광고를 나타낼지 고르고 선택된 사용자의 광고비만 지불하면 된다. 광고가 사용자의 담벼락에 게시되었을 때, 사용자의 친구들 모두와 자기 자신은 그 광고를 볼 수 있다. 이러한 방식으로 더 많은 사용자들에 광고를 알리기 위해 광고주는 적은 수의 광고비용만 지불하면 된다.

해빈이는 진욱이의 소셜 네트워크에 광고를 게시하고 싶어한다. 해빈이는 이미 사용자들의 "친구 목록" 을 가지고 있으며 이 그룹의 모든 사용자들이 광고를 보기 위해서 해빈이가 특정 사용자들의 담벼락에 게시해야 하는 최소의 광고 수를 구하여라.

진욱이의 소셜 네트워크에서는 A와 B가 친구이면 B도 A와 친구이다.

입력

입력은 여러개의 테스트 케이스로 이루어져 있다. 첫째 줄은 테스트 케이스를 나타낸다. 각각의 케이스마다 전체 사용자의 수 n (1 ≤ n ≤ 20) 이 주어진다. 다음 n개의 줄에는 친구의 목록이 입력으로 주어지는데 각각의 줄은 친구의 수 d (0 ≤ d < n) 가 먼저 입력으로 주어지고 뒤이어 d개의 친구 번호가 주어진다. i번째 줄은 i번째 사용자를 뜻하며 자기 자신이 친구일 수는 없다.

출력

각각의 케이스 마다 모든 사용자들이 광고를 볼수 있도록 해빈이가 게시하여야 하는 최소의 광고 수를 출력한다.

예제 입력 1

2
5
4 2 3 4 5
4 1 3 4 5
4 1 2 4 5
4 1 2 3 5
4 1 2 3 4
5
2 4 5
2 3 5
1 2
2 1 5
3 1 2 4

예제 출력 1

1
2
W3sicHJvYmxlbV9pZCI6IjkzMzUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxOGNcdWMxNWMgXHVhZDExXHVhY2UwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM5YzRcdWM2YjFcdWM3NzRcdWIyOTQgXHVjMGM4XHViODVjXHVjNmI0IFx1YzE4Y1x1YzE1YyBcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwYjkgXHVkNjhjXHVjMGFjXHViOTdjIFx1YjljY1x1YjRlNFx1YWUzMFx1Yjg1YyBcdWFjYjBcdWMyZWNcdWQ1ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWFlMzBcdWM4NzRcdWM3NTggXHVkMzk4XHVjNzc0XHVjMmE0XHViZDgxIFx1Yzc3NFx1YjA5OCBcdWQyYjhcdWM3MDRcdWQxMzAgXHVhYzE5XHVjNzc0IFx1Yzc3OFx1YWUzMFx1Yzc4OFx1YjI5NCBcdWMxOGNcdWMxNWMgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjIFx1YzExY1x1YmU0NFx1YzJhNFx1YjI5NCBcdWM3NzRcdWJiZjggXHVjMjE4XHVjMmVkXHVjNWI1XHVjNzU4IFx1YzBhY1x1YzZhOVx1Yzc5MFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVhY2UwLCBcdWM5YzRcdWM2YjFcdWM3NzRcdWIyOTQgXHVjNzc0XHViNGU0XHVhY2ZjIFx1YWNiZFx1YzdjMVx1YzVkMFx1YzExYyBcdWMyYjlcdWI5YWNcdWQ1NThcdWIyOTQgXHVjNzIwXHVjNzdjXHVkNTVjIFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWIyZTRcdWI5NzggXHVjMThjXHVjMTVjIFx1YjEyNFx1ZDJiOFx1YzZjY1x1ZDA2Y1x1YWMwMCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVhZTMwXHViMmE1XHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWI3N2MgXHVjMGRkXHVhYzAxXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5YzRcdWM2YjFcdWM3NzRcdWIyOTQgXHVhZDExXHVhY2UwXHVjOGZjXHVjNWQwXHVhYzhjIFx1YWMxMlx1YzJmYyBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgXHVhZDExXHVhY2UwXHViZTQ0XHViOTdjIFx1Y2NhZFx1YWQ2Y1x1ZDU2MCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjMGRkXHVhYzAxXHVkNTc0XHViMGM4XHViMmU0LiBcdWFkMTFcdWFjZTBcdWM4ZmNcdWIyOTQgXHVjNWI0XHViNWE0IFx1YzBhY1x1YzZhOVx1Yzc5MFx1Yzc1OCBcdWIyZjRcdWJjYmNcdWI3N2RcdWM1ZDAgXHVhZDExXHVhY2UwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiY1x1YzljMCBcdWFjZTBcdWI5NzRcdWFjZTAgXHVjMTIwXHVkMGRkXHViNDFjIFx1YzBhY1x1YzZhOVx1Yzc5MFx1Yzc1OCBcdWFkMTFcdWFjZTBcdWJlNDRcdWI5Y2MgXHVjOWMwXHViZDg4XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC4gXHVhZDExXHVhY2UwXHVhYzAwIFx1YzBhY1x1YzZhOVx1Yzc5MFx1Yzc1OCBcdWIyZjRcdWJjYmNcdWI3N2RcdWM1ZDAgXHVhYzhjXHVjMmRjXHViNDE4XHVjNWM4XHVjNzQ0IFx1YjU0YywgXHVjMGFjXHVjNmE5XHVjNzkwXHVjNzU4IFx1Y2U1Y1x1YWQ2Y1x1YjRlNCBcdWJhYThcdWI0NTBcdWM2NDAgXHVjNzkwXHVhZTMwIFx1Yzc5MFx1YzJlMFx1Yzc0MCBcdWFkZjggXHVhZDExXHVhY2UwXHViOTdjIFx1YmNmYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHViYzI5XHVjMmRkXHVjNzNjXHViODVjIFx1YjM1NCBcdWI5Y2VcdWM3NDAgXHVjMGFjXHVjNmE5XHVjNzkwXHViNGU0XHVjNWQwIFx1YWQxMVx1YWNlMFx1Yjk3YyBcdWM1NGNcdWI5YWNcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YWQxMVx1YWNlMFx1YzhmY1x1YjI5NCBcdWM4MDFcdWM3NDAgXHVjMjE4XHVjNzU4IFx1YWQxMVx1YWNlMFx1YmU0NFx1YzZhOVx1YjljYyBcdWM5YzBcdWJkODhcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NzRcdWJlNDhcdWM3NzRcdWIyOTQgXHVjOWM0XHVjNmIxXHVjNzc0XHVjNzU4IFx1YzE4Y1x1YzE1YyBcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmNcdWM1ZDAgXHVhZDExXHVhY2UwXHViOTdjIFx1YWM4Y1x1YzJkY1x1ZDU1OFx1YWNlMCBcdWMyZjZcdWM1YjRcdWQ1NWNcdWIyZTQuIFx1ZDU3NFx1YmU0OFx1Yzc3NFx1YjI5NCBcdWM3NzRcdWJiZjggXHVjMGFjXHVjNmE5XHVjNzkwXHViNGU0XHVjNzU4ICZxdW90O1x1Y2U1Y1x1YWQ2YyZuYnNwO1x1YmFhOVx1Yjg1ZCZxdW90OyBcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YzczY1x1YmE3MCBcdWM3NzQgXHVhZGY4XHViOGY5XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWMwYWNcdWM2YTlcdWM3OTBcdWI0ZTRcdWM3NzQgXHVhZDExXHVhY2UwXHViOTdjIFx1YmNmNFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVkNTc0XHViZTQ4XHVjNzc0XHVhYzAwIFx1ZDJiOVx1YzgxNSBcdWMwYWNcdWM2YTlcdWM3OTBcdWI0ZTRcdWM3NTggXHViMmY0XHViY2JjXHViNzdkXHVjNWQwIFx1YWM4Y1x1YzJkY1x1ZDU3NFx1YzU3YyZuYnNwO1x1ZDU1OFx1YjI5NCBcdWNkNWNcdWMxOGNcdWM3NTggXHVhZDExXHVhY2UwIFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuXHJcbjxwPlx1YzljNFx1YzZiMVx1Yzc3NFx1Yzc1OCBcdWMxOGNcdWMxNWMgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjXHVjNWQwXHVjMTFjXHViMjk0IEFcdWM2NDAgQlx1YWMwMCBcdWNlNWNcdWFkNmNcdWM3NzRcdWJhNzQgQlx1YjNjNCBBXHVjNjQwIFx1Y2U1Y1x1YWQ2Y1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWNcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNzQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YzgwNFx1Y2NiNCBcdWMwYWNcdWM2YTlcdWM3OTBcdWM3NTggXHVjMjE4Jm5ic3A7biAoMSAmbGU7IG4gJmxlOyAyMCkgXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2U1Y1x1YWQ2Y1x1Yzc1OCBcdWJhYTlcdWI4NWRcdWM3NzQgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCBcdWFjMDFcdWFjMDFcdWM3NTggXHVjOTA0XHVjNzQwIFx1Y2U1Y1x1YWQ2Y1x1Yzc1OCBcdWMyMTgmbmJzcDtkICgwICZsZTsgZCAmbHQ7IG4pIFx1YWMwMCBcdWJhM2NcdWM4MDAgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCBcdWI0YTRcdWM3NzRcdWM1YjQgZFx1YWMxY1x1Yzc1OCBcdWNlNWNcdWFkNmMgXHViYzg4XHVkNjM4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDtpXHViYzg4XHVjOWY4IFx1YzkwNFx1Yzc0MCBpXHViYzg4XHVjOWY4IFx1YzBhY1x1YzZhOVx1Yzc5MFx1Yjk3YyBcdWI3M2JcdWQ1NThcdWJhNzAgXHVjNzkwXHVhZTMwIFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWNlNWNcdWFkNmNcdWM3N2MmbmJzcDtcdWMyMThcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWNmMDBcdWM3NzRcdWMyYTQmbmJzcDtcdWI5YzhcdWIyZTQgXHViYWE4XHViNGUwIFx1YzBhY1x1YzZhOVx1Yzc5MFx1YjRlNFx1Yzc3NCBcdWFkMTFcdWFjZTBcdWI5N2MgXHViY2ZjXHVjMjE4IFx1Yzc4OFx1YjNjNFx1Yjg1ZCBcdWQ1NzRcdWJlNDhcdWM3NzRcdWFjMDAgXHVhYzhjXHVjMmRjXHVkNTU4XHVjNWVjXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWNkNWNcdWMxOGNcdWM3NTggXHVhZDExXHVhY2UwIFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTMzNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNvY2lhbCBBZHZlcnRpc2luZyIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGhhdmUgZGVjaWRlZCB0byBzdGFydCB1cCBhIG5ldyBzb2NpYWwgbmV0d29ya2luZyBjb21wYW55LiBPdGhlciBleGlzdGluZyBwb3B1bGFyIHNvY2lhbCBuZXR3b3JrcyBhbHJlYWR5IGhhdmUgYmlsbGlvbnMgb2YgdXNlcnMsIHNvIHRoZSBvbmx5IHdheSB0byBjb21wZXRlIHdpdGggdGhlbSBpcyB0byBpbmNsdWRlIG5vdmVsIGZlYXR1cmVzIG5vIG90aGVyIG5ldHdvcmtzIGhhdmUuPFwvcD5cclxuXHJcbjxwPllvdXIgY29tcGFueSBoYXMgZGVjaWRlZCB0byBtYXJrZXQgdG8gYWR2ZXJ0aXNlcnMgYSBjaGVhcGVyIHdheSB0byBjaGFyZ2UgZm9yIGFkdmVydGlzZW1lbnRzIChhZHMpLiBUaGUgYWR2ZXJ0aXNlciBjaG9vc2VzIHdoaWNoIHVzZXJzJnJzcXVvOyAmbGRxdW87d2FsbCZyZHF1bzsgdGhlIGFkcyB3b3VsZCBhcHBlYXIgb24sIGFuZCBvbmx5IHRob3NlIGFkcyBhcmUgY2hhcmdlZC4gV2hlbiBhbiBhZCBpcyBwb3N0ZWQgb24gYSB1c2VyJnJzcXVvO3Mgd2FsbCwgYWxsIG9mIGhpc1wvaGVyIGZyaWVuZHMgKGFuZCBvZiBjb3Vyc2UgdGhlIHVzZXIgaGltc2VsZlwvaGVyc2VsZikgd2lsbCBzZWUgdGhlIGFkLiBJbiB0aGlzIHdheSwgYW4gYWR2ZXJ0aXNlciBvbmx5IGhhcyB0byBwYXkgZm9yIGEgc21hbGwgbnVtYmVyIG9mIGFkcyB0byByZWFjaCBtYW55IG1vcmUgdXNlcnMuPFwvcD5cclxuXHJcbjxwPllvdSB3b3VsZCBsaWtlIHRvIHBvc3QgYWRzIHRvIGEgcGFydGljdWxhciBncm91cCBvZiB1c2VycyB3aXRoIHRoZSBtaW5pbXVtIGNvc3QuIFlvdSBhbHJlYWR5IGhhdmUgdGhlICZsZHF1bztmcmllbmRzIGxpc3QmcmRxdW87IG9mIGVhY2ggb2YgdGhlc2UgdXNlcnMsIGFuZCB5b3Ugd2FudCB0byBkZXRlcm1pbmUgdGhlIHNtYWxsZXN0IG51bWJlciBvZiBhZHMgeW91IGhhdmUgdG8gcG9zdCBpbiBvcmRlciB0byByZWFjaCBldmVyeSB1c2VyIGluIHRoaXMgZ3JvdXAuIEluIHRoaXMgc29jaWFsIG5ldHdvcmssIGlmIEEgaXMgYSBmcmllbmQgb2YgQiwgdGhlbiBCIGlzIGFsc28gYSBmcmllbmQgb2YgQSBmb3IgYW55IHR3byB1c2VycyBBIGFuZCBCLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIG11bHRpcGxlIHRlc3QgY2FzZXMuIFRoZSBcdWZiMDFyc3QgbGluZSBvZiBpbnB1dCBpcyBhIHNpbmdsZSBpbnRlZ2VyLCBub3QgbW9yZSB0aGFuIDEwLCBpbmRpY2F0aW5nIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyB0byBmb2xsb3cuIEVhY2ggY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyBhbiBpbnRlZ2VyIG4gKDEgJmxlOyBuICZsZTsgMjApIGluZGljYXRpbmcgdGhlIG51bWJlciBvZiB1c2VycyBpbiB0aGUgZ3JvdXAuIEZvciB0aGUgbmV4dCBuIGxpbmVzLCB0aGUgaXRoIGxpbmUgY29udGFpbnMgdGhlIGZyaWVuZCBsaXN0IG9mIHVzZXIgaSAodXNlcnMgYXJlIGxhYmVsbGVkIDEsIC4uLiAsIG4pLiBFYWNoIGxpbmUgc3RhcnRzIHdpdGggYW4gaW50ZWdlciBkICgwICZsZTsgZCAmbHQ7IG4pIGZvbGxvd2VkIGJ5IGQgbGFiZWxzIG9mIHRoZSBmcmllbmRzLiBObyB1c2VyIGlzIGEgZnJpZW5kIG9mIGhpbXNlbGZcL2hlcnNlbGYuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggY2FzZSwgZGlzcGxheSBvbiBhIGxpbmUgdGhlIG1pbmltdW0gbnVtYmVyIG9mIGFkcyBuZWVkZWQgdG8gYmUgcGxhY2VkIGluIG9yZGVyIGZvciB0aGVtIHRvIHJlYWNoIHRoZSBlbnRpcmUgZ3JvdXAgb2YgdXNlcnMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > North America > Rocky Mountain Regional > 2013 Rocky Mountain Regional Contest G번