시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHViMzAwXHVkNjhjXHVjNWQwXHVjMTFjIFx1YzBhY1x1YzZhOVx1ZDU3NFx1YzU3YyBcdWQ1NjAgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQwIDFcdWJkODBcdWQxMzAgTVx1YWU0Y1x1YzljMFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViYTcwLCBcdWJiMzhcdWM4MWNcdWIyOTQgXHVjY2FiXHViYzg4XHVjOWY4IFx1YmIzOFx1YzgxY1x1YWMwMCBBLCBcdWI0NTBcdWJjODhcdWM5ZjggXHViYjM4XHVjODFjXHVhYzAwIEIsIFx1YzEzOFx1YmM4OFx1YzlmOCBcdWJiMzhcdWM4MWNcdWFjMDAgQy4uIFx1Yzc1OCBcdWJjMjlcdWMyZGRcdWM3M2NcdWI4NWMgXHVjNzc0XHViOTg0XHVjNzQ0IFx1YmQ5OVx1Yzc3OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjNWI0XHVjMTFjIE5cdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1Y2NhYlx1YmM4OFx1YzlmOCBcdWJiMzhcdWM4MWNcdWJkODBcdWQxMzAgTlx1YmM4OFx1YzlmOCBcdWJiMzhcdWM4MWNcdWFlNGNcdWM5YzAgXHVjNWI0XHViNWE0IFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OFx1YjRlNFx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NThcdWIyOTRcdWM5YzBcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgRGF0YSBTZXQgSzogXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1YyBcdWI0YTQsIDFcdWJkODBcdWQxMzAgTVx1YWU0Y1x1YzljMFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWQwNmNcdWFlMzBcdWM3NTggXHViYjM4XHVjODFjIFx1YzEzOFx1ZDJiOFx1YzVkMCBcdWMxOGRcdWQ1NWMgXHViYjM4XHVjODFjXHViNGU0XHVjNzQ0IFx1YzBhY1x1YzgwNFx1YzIxY1x1YzczY1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljY1x1Yzc3YyBcdWIyZjVcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yjc3Y1x1YmE3NCBcdWFkZjggXHVjOTExIFx1YzBhY1x1YzgwNFx1YzIxY1x1YzczY1x1Yjg1YyBcdWFjMDBcdWM3YTUgXHVjNTVlXHVjMTIwIFx1YWM4M1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwXHVjMTFjIFx1YjJmNVx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzBhY1x1Yzc3NFx1YzVkNCBcdWJlNDggXHVjOTA0XHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTE3NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdvdCBwcm9ibGVtcz8iLCJkZXNjcmlwdGlvbiI6IjxwPkluIHByZXBhcmF0aW9uIGZvciB0aGUgY29udGVzdCwgd2UgY2FtZSB1cCB3aXRoIGEgbnVtYmVyIG9mIGFsZ29yaXRobXMgYW5kIHByb2dyYW1taW5nIHRvcGljcyB3ZSB3YW50IHRvIGNoZWNrLCBzdWNoIGFzIGdyYXBoIGFsZ29yaXRobXMsIGdlb21ldHJ5LCBzZWFyY2hpbmcsIHNvcnRpbmcsIHN0cmluZyBwcm9jZXNzaW5nLCBldGMuPFwvcD5cclxuXHJcbjxwPkFsc28sIHdlIG1hZGUgdXAgYSBudW1iZXIgb2YgcHJvYmxlbXMgKG9uZSBvZiB3aGljaCB5b3UmcnNxdW87cmUgbG9va2luZyBhdCksIGFuZCBmb3IgZWFjaCBwcm9ibGVtIGRldGVybWluZWQgd2hpY2ggY2F0ZWdvcmllcyBpdCBmYWxscyBpbnRvLiBBIHByb2JsZW0gd2lsbCBhbHdheXMgYmVsb25nIHRvIGF0IGxlYXN0IG9uZSBjYXRlZ29yeSwgYnV0IGl0IGNhbiBiZWxvbmcgdG8gc2V2ZXJhbCBjYXRlZ29yaWVzLCBwb3RlbnRpYWxseSBldmVuIGFsbCBvZiB0aGVtLjxcL3A+XHJcblxyXG48cD5Ob3cgd2Ugd2FudCB0byBmaW5kIGEgc2V0IG9mIHByb2JsZW1zIHRoYXQgd2lsbCBjb3ZlciBhbGwgY2F0ZWdvcmllcy4gQW5kIGFzIGdvb2QgcHJvYmxlbXMgYXJlIGhhcmQgdG8gbWFrZSB1cCBhbmQgdGhlcmVmb3JlIHByZWNpb3VzLCB3ZSB3YW50IHRvIHVzZSBhcyBmZXcgcHJvYmxlbXMgYXMgcG9zc2libGUuIFlvdSBhcmUgdG8gd3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBzYXZlIHVzIGZyb20gZG9pbmcgdGhpcyBieSBoYW5kLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgd2lsbCBjb250YWluIHRoZSBudW1iZXIgSyBvZiBpbnB1dCBkYXRhIHNldHMuIFRoaXMgaXMgZm9sbG93ZWQgYnkgSyBkYXRhIHNldHMsIGVhY2ggb2YgdGhlIGZvbGxvd2luZyBmb3JtOjxcL3A+XHJcblxyXG48cD5UaGUgZmlyc3QgbGluZSBvZiBhIGRhdGEgc2V0IGNvbnRhaW5zIHR3byBudW1iZXJzLCBNIGFuZCBOICgxICZsZTsgTSwgTiAmbGU7IDIwKS4gTSBpcyB0aGUgbnVtYmVyIG9mIHByb2JsZW0gY2F0ZWdvcmllcywgYW5kIE4gaXMgdGhlIG51bWJlciBvZiBhdmFpbGFibGUgcHJvYmxlbXMuIFByb2JsZW0gY2F0ZWdvcmllcyBhcmUgZGVub3RlZCBieSAxLCAuIC4gLiAsIE0sIGFuZCBwcm9ibGVtcyBieSBBLCBCLCAuIC4gLi4gVGhlIGZvbGxvd2luZyBOIGxpbmVzIGVhY2ggY29udGFpbiB0aGUgbnVtYmVycyBvZiB0aGUgY2F0ZWdvcmllcyBjb3ZlcmVkIGJ5IGEgcHJvYmxlbSAmbWRhc2g7IHRoZSBmaXJzdCBsaW5lIGZvciBwcm9ibGVtIEEsIHRoZSBzZWNvbmQgb25lIGZvciBCLCBhbmQgc28gb24uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCBmaWxlIGNvbnRhaW5zIG9uZSBsaW5lIGZvciBlYWNoIGlucHV0LCBzZXBhcmF0ZWQgYnkgYW4gZW1wdHkgbGluZS4gRWFjaCBsaW5lIGNvbnRhaW5zIGZpcnN0IHRoZSBudW1iZXIgb2YgdGhlIGRhdGEgc2V0LCBhbmQgdGhlbiB0aGUgc29sdXRpb24uIFRoZSBzb2x1dGlvbiBpcyB0aGUgbGlzdCBvZiBwcm9ibGVtcyB0byBiZSB1c2VkLCBzZXBhcmF0ZWQgYnkgd2hpdGVzcGFjZSwgYW5kIHNvcnRlZCBhbHBoYWJldGljYWxseS48XC9wPlxyXG5cclxuPHA+WW91IG1heSBhc3N1bWUgdGhhdCB0aGVyZSBpcyBhbHdheXMgYSBzb2x1dGlvbiwgYnV0IGl0IG5lZWQgbm90IGJlIHVuaXF1ZS4gSWYgdGhlcmUgYXJlIHNldmVyYWwgYmVzdCBzb2x1dGlvbnMgKGkuZS4gb2YgZXF1YWwgbGVuZ3RoKSwgb3V0cHV0IHRoZSBvbmUgd2hpY2ggY29tZXMgYWxwaGFiZXRpY2FsbHkgZmlyc3QgaW4gdGhlIG91dHB1dCBmb3JtYXQganVzdCBkZXNjcmliZWQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

University > The USC Programming Contest > Fall 2007 A번