콩도르세 역설

콩도르세 승자는 다른 모든 후보를 일대일 대결에서 이기는 후보이다. 콩도르세 승자는 각 유권자가 자신이 선호하는 순서대로 모든 후보를 적는 방식의 투표에서만 결정할 수 있으며, 이때 사용하는 투표용지를 선호 리스트라고 한다.

후보 X가 후보 Y를 일대일로 이긴다는 것은, 전체 투표용지의 과반수(즉 절반을 초과하는 수)에서 X가 Y보다 앞 순위에 적혀 있다는 뜻이다. 모든 투표용지는 모든 후보의 순위를 매기므로, 임의의 두 후보에 대해 각 투표용지에서 정확히 한 쪽이 더 앞선다. 따라서 X는 절반을 초과하는 투표용지에서 Y보다 선호될 때 Y를 이긴다.

예를 들어 후보가 A, B, C 세 명이고 유권자 세 명의 선호 리스트가 각각 ABC, BAC, CBA라고 하자. 이때 콩도르세 승자는 B이다. B는 두 장의 투표용지(2번, 3번)에서 A보다 앞서고, 두 장(1번, 2번)에서 C보다 앞선다. 참고로 만약 이 예시를 보통의 다수 득표 방식(각 유권자의 1순위만 세는 방식)으로 처리하면 세 후보가 모두 동점이 된다.

콩도르세 승자는 많아야 한 명이지만, 존재하지 않을 수도 있다. 선호 리스트가 주어졌을 때 콩도르세 승자를 구하시오.

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

각 테스트 케이스마다 Case k: w를 출력한다. 여기서 k는 테스트 케이스 번호(1부터 시작)이고 w는 콩도르세 승자의 번호이다. 콩도르세 승자가 없으면 대신 Case k: No Condorcet winner를 출력한다.