시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 58 5 5 13.514%

문제

콩도르세 승자는 선거에서 다른 모든 후보를 1:1로 이길 수 있는 후보자이다. 콩도르세 승자는 투표자가 자신이 선호하는 순서대로 투표자를 모두 적는 투표 방식에서만 결정할 수 있다. 이때 사용하는 투표용지를 선호 리스트라고 한다.

예를 들어, 후보가 3명 A, B, C이고, 투표자가 세 명일 때 선호 리스트에 ABC, BAC, CBA와 같이 적혀져있다고 하자. 이 경우에 콩도르세 승자는 B이다. B는 A를 2번 (2, 3)이기고, C를 2번 (1, 2) 이긴다.

콩도르세 투표 시스템에서 당선자는 콩도르세 승자이다. 만약 위의 예제가 보통 투표 방식(1등만)을 사용한다면, 모두 동점이 된다. 콩도르세 투표에서 콩도르세 승자는 한 명을 넘을 수 없다. 하지만, 콩도르세 승자가 없을 수도 있다.

선호 리스트가 주어졌을 때, 콩도르세 승자를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 선호 리스트의 수 b와 후보자의 수 c가 주어진다. (1 ≤ b ≤ 500, 1 ≤ c ≤ 2500) 후보자는 0번부터 c-1번까지 번호가 매겨져 있다. 다음 줄부터 b개 줄에는 각 선호 리스트에 적혀있는 후보자가 순서대로 주어진다.

입력의 마지막 줄에는 0 0이 주어진다.

출력

각 테스트 케이스에 대해서 콩도르세 승자를 출력한다. 만약, 승자가 없는 경우에는 No Condorcet winner를 출력한다.

예제 입력 1

3 3
0 1 2
1 0 2
2 1 0
3 3
0 1 2
1 2 0
2 0 1
0 0

예제 출력 1

Case 1: 1
Case 2: No Condorcet winner
W3sicHJvYmxlbV9pZCI6IjQwMjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNmNjlcdWIzYzRcdWI5NzRcdWMxMzggXHVjNWVkXHVjMTI0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWNmNjlcdWIzYzRcdWI5NzRcdWMxMzggXHVjMmI5XHVjNzkwXHViMjk0IFx1YzEyMFx1YWM3MFx1YzVkMFx1YzExYyBcdWIyZTRcdWI5NzggXHViYWE4XHViNGUwIFx1ZDZjNFx1YmNmNFx1Yjk3YyAxOjFcdWI4NWMgXHVjNzc0XHVhZTM4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVkNmM0XHViY2Y0XHVjNzkwXHVjNzc0XHViMmU0LiBcdWNmNjlcdWIzYzRcdWI5NzRcdWMxMzggXHVjMmI5XHVjNzkwXHViMjk0IFx1ZDIyY1x1ZDQ1Y1x1Yzc5MFx1YWMwMCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVjMTIwXHVkNjM4XHVkNTU4XHViMjk0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWQyMmNcdWQ0NWNcdWM3OTBcdWI5N2MgXHViYWE4XHViNDUwIFx1YzgwMVx1YjI5NCBcdWQyMmNcdWQ0NWMgXHViYzI5XHVjMmRkXHVjNWQwXHVjMTFjXHViOWNjIFx1YWNiMFx1YzgxNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI1NGMgXHVjMGFjXHVjNmE5XHVkNTU4XHViMjk0IFx1ZDIyY1x1ZDQ1Y1x1YzZhOVx1YzljMFx1Yjk3YyBcdWMxMjBcdWQ2MzggXHViOWFjXHVjMmE0XHVkMmI4XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVkNmM0XHViY2Y0XHVhYzAwIDNcdWJhODUgQSwgQiwgQ1x1Yzc3NFx1YWNlMCwgXHVkMjJjXHVkNDVjXHVjNzkwXHVhYzAwIFx1YzEzOCBcdWJhODVcdWM3N2MgXHViNTRjIFx1YzEyMFx1ZDYzOCBcdWI5YWNcdWMyYTRcdWQyYjhcdWM1ZDAgQUJDLCBCQUMsIENCQVx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjODAxXHVkNjAwXHVjODM4XHVjNzg4XHViMmU0XHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjNzc0IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWNmNjlcdWIzYzRcdWI5NzRcdWMxMzggXHVjMmI5XHVjNzkwXHViMjk0IEJcdWM3NzRcdWIyZTQuIEJcdWIyOTQgQVx1Yjk3YyAyXHViYzg4ICgyLCAzKVx1Yzc3NFx1YWUzMFx1YWNlMCwgQ1x1Yjk3YyAyXHViYzg4ICgxLCAyKSBcdWM3NzRcdWFlMzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2Y2OVx1YjNjNFx1Yjk3NFx1YzEzOCBcdWQyMmNcdWQ0NWMgXHVjMmRjXHVjMmE0XHVkMTVjXHVjNWQwXHVjMTFjIFx1YjJmOVx1YzEyMFx1Yzc5MFx1YjI5NCBcdWNmNjlcdWIzYzRcdWI5NzRcdWMxMzggXHVjMmI5XHVjNzkwXHVjNzc0XHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVjNzA0XHVjNzU4IFx1YzYwOFx1YzgxY1x1YWMwMCBcdWJjZjRcdWQxYjUgXHVkMjJjXHVkNDVjIFx1YmMyOVx1YzJkZCgxXHViNGYxXHViOWNjKVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTRcdWJhNzQsIFx1YmFhOFx1YjQ1MCBcdWIzZDlcdWM4MTBcdWM3NzQgXHViNDFjXHViMmU0LiBcdWNmNjlcdWIzYzRcdWI5NzRcdWMxMzggXHVkMjJjXHVkNDVjXHVjNWQwXHVjMTFjIFx1Y2Y2OVx1YjNjNFx1Yjk3NFx1YzEzOCBcdWMyYjlcdWM3OTBcdWIyOTQgXHVkNTVjIFx1YmE4NVx1Yzc0NCBcdWIxMThcdWM3NDQgXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWNmNjlcdWIzYzRcdWI5NzRcdWMxMzggXHVjMmI5XHVjNzkwXHVhYzAwIFx1YzVjNlx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMjBcdWQ2MzggXHViOWFjXHVjMmE0XHVkMmI4XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Y2Y2OVx1YjNjNFx1Yjk3NFx1YzEzOCBcdWMyYjlcdWM3OTBcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMTIwXHVkNjM4IFx1YjlhY1x1YzJhNFx1ZDJiOFx1Yzc1OCBcdWMyMTggYlx1YzY0MCBcdWQ2YzRcdWJjZjRcdWM3OTBcdWM3NTggXHVjMjE4IGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IGIgJmxlOyA1MDAsIDEgJmxlOyBjICZsZTsgMjUwMCkgXHVkNmM0XHViY2Y0XHVjNzkwXHViMjk0IDBcdWJjODhcdWJkODBcdWQxMzAgYy0xXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjOTA0XHViZDgwXHVkMTMwIGJcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWMxMjBcdWQ2MzggXHViOWFjXHVjMmE0XHVkMmI4XHVjNWQwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWQ2YzRcdWJjZjRcdWM3OTBcdWFjMDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMCAwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVjZjY5XHViM2M0XHViOTc0XHVjMTM4IFx1YzJiOVx1Yzc5MFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVjMmI5XHVjNzkwXHVhYzAwIFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgTm8gQ29uZG9yY2V0IHdpbm5lclx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDAyOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNvbmRvcmNldCBXaW5uZXJzIiwiZGVzY3JpcHRpb24iOiI8cD5BIENvbmRvcmNldCB3aW5uZXIgb2YgYW4gZWxlY3Rpb24gaXMgYSBjYW5kaWRhdGUgd2hvIHdvdWxkIGJlYXQgYW55IG9mIHRoZSBvdGhlciBjYW5kaWRhdGVzIGluIGEgb25lLW9uLW9uZSBjb250ZXN0LiBEZXRlcm1pbmluZyBhIENvbmRvcmNldCB3aW5uZXIgY2FuIG9ubHkgYmUgZG9uZSB3aGVuIHZvdGVycyBzcGVjaWZ5IGEgYmFsbG90IGxpc3RpbmcgYWxsIG9mIHRoZSBjYW5kaWRhdGVzIGluIHRoZWlyIG9yZGVyIG9mIHByZWZlcmVuY2UgKHdlIHdpbGwgY2FsbCBzdWNoIGEgYmFsbG90IGEgcHJlZmVyZW5jZSBsaXN0KS4gRm9yIGV4YW1wbGUsIGFzc3VtZSB3ZSBoYXZlIDMgY2FuZGlkYXRlcyAtIEEsIEIgYW5kIEMgLSBhbmQgdGhyZWUgdm90ZXJzIHdob3NlIHByZWZlcmVuY2UgbGlzdHMgYXJlIEFCQywgQkFDLCBDQkEuIEhlcmUsIEIgaXMgdGhlIENvbmRvcmNldCB3aW5uZXIsIGJlYXRpbmcgQSBpbiAyIG9mIHRoZSB0aHJlZSBiYWxsb3RzIChiYWxsb3RzIDIgYW5kIDMpIGFuZCBiZWF0aW5nIEMgaW4gMiBvZiB0aGUgdGhyZWUgYmFsbG90cyAoMSBhbmQgMikuPFwvcD5cclxuXHJcbjxwPlRoZSBDb25kb3JjZXQgdm90aW5nIHN5c3RlbSBsb29rcyBmb3IgdGhlIENvbmRvcmNldCB3aW5uZXIgYW5kIGRlY2xhcmVzIHRoYXQgcGVyc29uIHRoZSB3aW5uZXIgb2YgdGhlIGVsZWN0aW9uLiBOb3RlIHRoYXQgaWYgd2Ugd2VyZSBvbmx5IGNvbnNpZGVyaW5nIHJzdCBwbGFjZSB2b3RlcyBpbiB0aGUgZXhhbXBsZSBhYm92ZSAoYXMgd2UgZG8gaW4gbW9zdCBlbGVjdGlvbnMgaW4gdGhlIFVTIGFuZCBDYW5hZGEpLCB0aGVuIHRoZXJlIHdvdWxkIGJlIGEgdGllIGZvciByc3QgcGxhY2UuIFRoZXJlIGNhbiBiZSBhdCBtb3N0IG9ubHkgb25lIENvbmRvcmNldCB3aW5uZXIsIGJ1dCB0aGVyZSBpcyBvbmUgc21hbGwgZHJhd2JhY2sgaW4gdGhlIENvbmRvcmNldCBzeXN0ZW0gfCBpdCBpcyBwb3NzaWJsZSB0aGF0IHRoZXJlIG1heSBiZSBubyBDb25kb3JjZXQgd2lubmVyLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgZm9yIGVhY2ggdGVzdCBjYXNlIHdpbGwgc3RhcnQgd2l0aCBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgdHdvIHBvc2l0aXZlIGludGVnZXJzIGIgYywgd2hlcmUgYiBpbmRpY2F0ZXMgdGhlIG51bWJlciBvZiBiYWxsb3RzIGFuZCBjIGluZGljYXRlcyB0aGUgbnVtYmVyIG9mIGNhbmRpZGF0ZXMuIENhbmRpZGF0ZXMgYXJlIGNvbnNpZGVyZWQgbnVtYmVyZWQgMCwgLi4uLCBjIC0gMS4gRm9sbG93aW5nIHRoaXMgcnN0IGxpbmUgd2lsbCBiZSBiIGxpbmVzIGNvbnRhaW5pbmcgYyB2YWx1ZXMgZWFjaC4gRWFjaCBvZiB0aGVzZSBsaW5lcyByZXByZXNlbnRzIG9uZSBiYWxsb3QgYW5kIHdpbGwgY29udGFpbiB0aGUgdmFsdWVzIDAsIC4uLiwgYyAtIDEgaW4gc29tZSBwZXJtdXRlZCBvcmRlci4gVmFsdWVzIG9mIGIgYW5kIGMgd2lsbCBsaWUgaW4gdGhlIHJhbmdlcyAxIC4uLiA1MDAgYW5kIDEgLi4uIDI1MDAsIHJlc3BlY3RpdmVseSwgYW5kIHRoZSBsaW5lIDAgMCB3aWxsIGZvbGxvdyB0aGUgbGFzdCB0ZXN0IGNhc2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIG91dHB1dCBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgZWl0aGVyIHRoZSBjYW5kaWRhdGUgbnVtYmVyIG9mIHRoZSBDb25kb3JjZXQgd2lubmVyLCBvciB0aGUgcGhyYXNlIE5vIENvbmRvcmNldCB3aW5uZXIgdXNpbmcgdGhlIGZvcm1hdCBnaXZlbi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=