시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 9 4 4 44.444%

문제

ACM 코더들은 보편적으로 사용하는 많은 알고리즘들에 대한 이해도가 폭넓게 높아야 한다. 그래서 일반적으로 ACM 대회를 개최할 땐 되도록이면 많은 알고리즘을 두루두루 사용하게끔 문제를 낸다.

하지만 어떤 대회에서, 문제 전체에서 단 한 번도 사용되지 않는 알고리즘이 하나라도 존재한다면 그건 문제 있는 문제 세트이다. 예를 들면 DP가 없거나, 그래프 이론과 관련된 알고리즘이 없는 문제 세트는 문제가 있다는 것이다.

이번 문제에서는 이번 대회를 위해 만든 문제 세트에 대하여, 문제들의 부분집합으로 이루어진 문제 세트들 중 문제 없는 문제 세트를 만들어볼 것이다. 세트 내에서 어떤 알고리즘이 너무 많이 사용되는 것은 상관없으나, 모든 알고리즘들을 반드시 한 번 이상 사용해야만 한다.

하지만 문제를 만드는 것은 매우 어려운 일이기 때문에 되도록이면 적은 문제로 이루어진 세트를 찾아야 한다. 그렇게 해야 남는 문제를 다음 대회에 사용할 수가 있다.

입력

첫 줄에 테스트 케이스의 수 K가 주어진다.

각 테스트 케이스의 첫 줄엔 두 정수 M과 N이 주어진다. (1 ≤ M, N ≤ 20)

M은 대회에서 사용할 알고리즘의 개수이며, N은 문제의 총 개수이다.

대회에서 사용해야 할 알고리즘은 1부터 M까지의 모든 자연수이며, 문제는 첫 번째 문제가 A, 두 번째 문제가 B, 세 번째 문제가 C.. 의 방식으로 이름을 붙인다.

이어서 N줄에 걸쳐 첫 번째 문제부터 N번째 문제까지 어떤 알고리즘들을 사용하는지가 공백으로 구분되어 주어진다.

출력

각 테스트 케이스마다 Data Set K: 를 출력한 뒤, 1부터 M까지의 모든 알고리즘을 포함할 수 있는 최소 크기의 문제 세트에 속한 문제들을 사전순으로 출력한다.

만일 답이 여러 가지라면 그 중 사전순으로 가장 앞선 것을 출력한다.

모든 테스트 케이스에서 답이 존재하지 않는 경우는 없다.

각 테스트 케이스의 사이엔 빈 줄을 하나 출력한다.

예제 입력 1

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

예제 출력 1

Data Set 1: C

Data Set 2: A C
W3sicHJvYmxlbV9pZCI6IjUxNzUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzhcdWM4MWNcdWM1YzZcdWIyOTQgXHViYjM4XHVjODFjIiwiZGVzY3JpcHRpb24iOiI8cD5BQ00gXHVjZjU0XHViMzU0XHViNGU0XHVjNzQwIFx1YmNmNFx1ZDNiOFx1YzgwMVx1YzczY1x1Yjg1YyBcdWMwYWNcdWM2YTlcdWQ1NThcdWIyOTQgXHViOWNlXHVjNzQwIFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OFx1YjRlNFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjNzc0XHVkNTc0XHViM2M0XHVhYzAwIFx1ZDNlZFx1YjExM1x1YWM4YyBcdWIxOTJcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHVjNzdjXHViYzE4XHVjODAxXHVjNzNjXHViODVjIEFDTSBcdWIzMDBcdWQ2OGNcdWI5N2MgXHVhYzFjXHVjZDVjXHVkNTYwIFx1YjU1MCBcdWI0MThcdWIzYzRcdWI4NWRcdWM3NzRcdWJhNzQgXHViOWNlXHVjNzQwIFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OFx1Yzc0NCBcdWI0NTBcdWI4ZThcdWI0NTBcdWI4ZTggXHVjMGFjXHVjNmE5XHVkNTU4XHVhYzhjXHViMDU0IFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1OFx1YzljMFx1YjljYyBcdWM1YjRcdWI1YTQgXHViMzAwXHVkNjhjXHVjNWQwXHVjMTFjLCBcdWJiMzhcdWM4MWMgXHVjODA0XHVjY2I0XHVjNWQwXHVjMTFjIFx1YjJlOCBcdWQ1NWMgXHViYzg4XHViM2M0IFx1YzBhY1x1YzZhOVx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTQgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzc0IFx1ZDU1OFx1YjA5OFx1Yjc3Y1x1YjNjNCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTRcdWJhNzQgXHVhZGY4XHVhYzc0IFx1YmIzOFx1YzgxYyBcdWM3ODhcdWIyOTQgXHViYjM4XHVjODFjIFx1YzEzOFx1ZDJiOFx1Yzc3NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YmE3NCBEUFx1YWMwMCBcdWM1YzZcdWFjNzBcdWIwOTgsIFx1YWRmOFx1Yjc5OFx1ZDUwNCBcdWM3NzRcdWI4NjBcdWFjZmMgXHVhZDAwXHViODI4XHViNDFjIFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OFx1Yzc3NCBcdWM1YzZcdWIyOTQgXHViYjM4XHVjODFjIFx1YzEzOFx1ZDJiOFx1YjI5NCBcdWJiMzhcdWM4MWNcdWFjMDAgXHVjNzg4XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViYzg4IFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExY1x1YjI5NCBcdWM3NzRcdWJjODggXHViMzAwXHVkNjhjXHViOTdjIFx1YzcwNFx1ZDU3NCBcdWI5Y2NcdWI0ZTAgXHViYjM4XHVjODFjIFx1YzEzOFx1ZDJiOFx1YzVkMCBcdWIzMDBcdWQ1NThcdWM1ZWMsIFx1YmIzOFx1YzgxY1x1YjRlNFx1Yzc1OCBcdWJkODBcdWJkODRcdWM5ZDFcdWQ1NjlcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1YzgxYyBcdWMxMzhcdWQyYjhcdWI0ZTQgXHVjOTExIFx1YmIzOFx1YzgxYyBcdWM1YzZcdWIyOTQgXHViYjM4XHVjODFjIFx1YzEzOFx1ZDJiOFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWJjZmMgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWMxMzhcdWQyYjggXHViMGI0XHVjNWQwXHVjMTFjIFx1YzViNFx1YjVhNCBcdWM1NGNcdWFjZTBcdWI5YWNcdWM5OThcdWM3NzQgXHViMTA4XHViYjM0IFx1YjljZVx1Yzc3NCBcdWMwYWNcdWM2YTlcdWI0MThcdWIyOTQgXHVhYzgzXHVjNzQwIFx1YzBjMVx1YWQwMFx1YzVjNlx1YzczY1x1YjA5OCwgXHViYWE4XHViNGUwIFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OFx1YjRlNFx1Yzc0NCBcdWJjMThcdWI0ZGNcdWMyZGMgXHVkNTVjIFx1YmM4OCBcdWM3NzRcdWMwYzEgXHVjMGFjXHVjNmE5XHVkNTc0XHVjNTdjXHViOWNjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjOWMwXHViOWNjIFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVhYzgzXHVjNzQwIFx1YjllNFx1YzZiMCBcdWM1YjRcdWI4MjRcdWM2YjQgXHVjNzdjXHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWI0MThcdWIzYzRcdWI4NWRcdWM3NzRcdWJhNzQgXHVjODAxXHVjNzQwIFx1YmIzOFx1YzgxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjMTM4XHVkMmI4XHViOTdjIFx1Y2MzZVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjgwN1x1YWM4YyBcdWQ1NzRcdWM1N2MgXHViMGE4XHViMjk0IFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWIyZTRcdWM3NGMgXHViMzAwXHVkNjhjXHVjNWQwIFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWMyMThcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOCBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiIFx1YzkwNFx1YzVkNCBcdWI0NTAgXHVjODE1XHVjMjE4IE1cdWFjZmMgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTSwgTiAmbGU7IDIwKTxcL3A+XHJcblxyXG48cD5NXHVjNzQwIFx1YjMwMFx1ZDY4Y1x1YzVkMFx1YzExYyBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3NFx1YmE3MCwgTlx1Yzc0MCBcdWJiMzhcdWM4MWNcdWM3NTggXHVjZDFkIFx1YWMxY1x1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMzAwXHVkNjhjXHVjNWQwXHVjMTFjIFx1YzBhY1x1YzZhOVx1ZDU3NFx1YzU3YyBcdWQ1NjAgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQwIDFcdWJkODBcdWQxMzAgTVx1YWU0Y1x1YzljMFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViYTcwLCBcdWJiMzhcdWM4MWNcdWIyOTQgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWJiMzhcdWM4MWNcdWFjMDAgQSwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWJiMzhcdWM4MWNcdWFjMDAgQiwgXHVjMTM4IFx1YmM4OFx1YzlmOCBcdWJiMzhcdWM4MWNcdWFjMDAgQy4uIFx1Yzc1OCBcdWJjMjlcdWMyZGRcdWM3M2NcdWI4NWMgXHVjNzc0XHViOTg0XHVjNzQ0IFx1YmQ5OVx1Yzc3OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjNWI0XHVjMTFjIE5cdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHViYjM4XHVjODFjXHViZDgwXHVkMTMwIE5cdWJjODhcdWM5ZjggXHViYjM4XHVjODFjXHVhZTRjXHVjOWMwIFx1YzViNFx1YjVhNCBcdWM1NGNcdWFjZTBcdWI5YWNcdWM5OThcdWI0ZTRcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTU4XHViMjk0XHVjOWMwXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IERhdGEgU2V0IEs6IFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWMgXHViNGE0LCAxXHViZDgwXHVkMTMwIE1cdWFlNGNcdWM5YzBcdWM3NTggXHViYWE4XHViNGUwIFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OFx1Yzc0NCBcdWQzZWNcdWQ1NjhcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWMxOGMgXHVkMDZjXHVhZTMwXHVjNzU4IFx1YmIzOFx1YzgxYyBcdWMxMzhcdWQyYjhcdWM1ZDAgXHVjMThkXHVkNTVjIFx1YmIzOFx1YzgxY1x1YjRlNFx1Yzc0NCBcdWMwYWNcdWM4MDRcdWMyMWNcdWM3M2NcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5Y2NcdWM3N2MgXHViMmY1XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWI3N2NcdWJhNzQgXHVhZGY4IFx1YzkxMSBcdWMwYWNcdWM4MDRcdWMyMWNcdWM3M2NcdWI4NWMgXHVhYzAwXHVjN2E1IFx1YzU1ZVx1YzEyMCBcdWFjODNcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMFx1YzExYyBcdWIyZjVcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMwYWNcdWM3NzRcdWM1ZDQgXHViZTQ4IFx1YzkwNFx1Yzc0NCBcdWQ1NThcdWIwOTggXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjUxNzUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHb3QgcHJvYmxlbXM/IiwiZGVzY3JpcHRpb24iOiI8cD5JbiBwcmVwYXJhdGlvbiBmb3IgdGhlIGNvbnRlc3QsIHdlIGNhbWUgdXAgd2l0aCBhIG51bWJlciBvZiBhbGdvcml0aG1zIGFuZCBwcm9ncmFtbWluZyB0b3BpY3Mgd2Ugd2FudCB0byBjaGVjaywgc3VjaCBhcyBncmFwaCBhbGdvcml0aG1zLCBnZW9tZXRyeSwgc2VhcmNoaW5nLCBzb3J0aW5nLCBzdHJpbmcgcHJvY2Vzc2luZywgZXRjLjxcL3A+XHJcblxyXG48cD5BbHNvLCB3ZSBtYWRlIHVwIGEgbnVtYmVyIG9mIHByb2JsZW1zIChvbmUgb2Ygd2hpY2ggeW91JnJzcXVvO3JlIGxvb2tpbmcgYXQpLCBhbmQgZm9yIGVhY2ggcHJvYmxlbSBkZXRlcm1pbmVkIHdoaWNoIGNhdGVnb3JpZXMgaXQgZmFsbHMgaW50by4gQSBwcm9ibGVtIHdpbGwgYWx3YXlzIGJlbG9uZyB0byBhdCBsZWFzdCBvbmUgY2F0ZWdvcnksIGJ1dCBpdCBjYW4gYmVsb25nIHRvIHNldmVyYWwgY2F0ZWdvcmllcywgcG90ZW50aWFsbHkgZXZlbiBhbGwgb2YgdGhlbS48XC9wPlxyXG5cclxuPHA+Tm93IHdlIHdhbnQgdG8gZmluZCBhIHNldCBvZiBwcm9ibGVtcyB0aGF0IHdpbGwgY292ZXIgYWxsIGNhdGVnb3JpZXMuIEFuZCBhcyBnb29kIHByb2JsZW1zIGFyZSBoYXJkIHRvIG1ha2UgdXAgYW5kIHRoZXJlZm9yZSBwcmVjaW91cywgd2Ugd2FudCB0byB1c2UgYXMgZmV3IHByb2JsZW1zIGFzIHBvc3NpYmxlLiBZb3UgYXJlIHRvIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgc2F2ZSB1cyBmcm9tIGRvaW5nIHRoaXMgYnkgaGFuZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIHdpbGwgY29udGFpbiB0aGUgbnVtYmVyIEsgb2YgaW5wdXQgZGF0YSBzZXRzLiBUaGlzIGlzIGZvbGxvd2VkIGJ5IEsgZGF0YSBzZXRzLCBlYWNoIG9mIHRoZSBmb2xsb3dpbmcgZm9ybTo8XC9wPlxyXG5cclxuPHA+VGhlIGZpcnN0IGxpbmUgb2YgYSBkYXRhIHNldCBjb250YWlucyB0d28gbnVtYmVycywgTSBhbmQgTiAoMSAmbGU7IE0sIE4gJmxlOyAyMCkuIE0gaXMgdGhlIG51bWJlciBvZiBwcm9ibGVtIGNhdGVnb3JpZXMsIGFuZCBOIGlzIHRoZSBudW1iZXIgb2YgYXZhaWxhYmxlIHByb2JsZW1zLiBQcm9ibGVtIGNhdGVnb3JpZXMgYXJlIGRlbm90ZWQgYnkgMSwgLiAuIC4gLCBNLCBhbmQgcHJvYmxlbXMgYnkgQSwgQiwgLiAuIC4uIFRoZSBmb2xsb3dpbmcgTiBsaW5lcyBlYWNoIGNvbnRhaW4gdGhlIG51bWJlcnMgb2YgdGhlIGNhdGVnb3JpZXMgY292ZXJlZCBieSBhIHByb2JsZW0gJm1kYXNoOyB0aGUgZmlyc3QgbGluZSBmb3IgcHJvYmxlbSBBLCB0aGUgc2Vjb25kIG9uZSBmb3IgQiwgYW5kIHNvIG9uLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgZmlsZSBjb250YWlucyBvbmUgbGluZSBmb3IgZWFjaCBpbnB1dCwgc2VwYXJhdGVkIGJ5IGFuIGVtcHR5IGxpbmUuIEVhY2ggbGluZSBjb250YWlucyBmaXJzdCB0aGUgbnVtYmVyIG9mIHRoZSBkYXRhIHNldCwgYW5kIHRoZW4gdGhlIHNvbHV0aW9uLiBUaGUgc29sdXRpb24gaXMgdGhlIGxpc3Qgb2YgcHJvYmxlbXMgdG8gYmUgdXNlZCwgc2VwYXJhdGVkIGJ5IHdoaXRlc3BhY2UsIGFuZCBzb3J0ZWQgYWxwaGFiZXRpY2FsbHkuPFwvcD5cclxuXHJcbjxwPllvdSBtYXkgYXNzdW1lIHRoYXQgdGhlcmUgaXMgYWx3YXlzIGEgc29sdXRpb24sIGJ1dCBpdCBuZWVkIG5vdCBiZSB1bmlxdWUuIElmIHRoZXJlIGFyZSBzZXZlcmFsIGJlc3Qgc29sdXRpb25zIChpLmUuIG9mIGVxdWFsIGxlbmd0aCksIG91dHB1dCB0aGUgb25lIHdoaWNoIGNvbWVzIGFscGhhYmV0aWNhbGx5IGZpcnN0IGluIHRoZSBvdXRwdXQgZm9ybWF0IGp1c3QgZGVzY3JpYmVkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

University > The USC Programming Contest > Fall 2007 A번