eolymp
bolt
Try our new interface for solving problems
Problems

Condorcet Winners

Condorcet Winners

A Condorcet winner of an election is a candidate who would beat any of the other candidates in a one-on-one contest. Determining a Condorcet winner can only be done when voters specify a ballot listing all of the candidates in their order of preference (we will call such a ballot a \textit{preference list}). For example, assume we have \textbf{3} candidates - \textbf{A}, \textbf{B} and \textbf{C} - and three voters whose preference lists are \textbf{ABC}, \textbf{BAC}, \textbf{CBA}. Here, \textbf{B} is the Condorcet winner, beating \textbf{A} in \textbf{2} of the three ballots (ballots \textbf{2} and \textbf{3}) and beating \textbf{C} in \textbf{2} of the three ballots (\textbf{1} and \textbf{2}). The \textit{Condorcet voting system} looks for the Condorcet winner and declares that person the winner of the election. Note that if we were only considering rst place votes in the example above (as we do in most elections in the US and Canada), then there would be a tie for rst place. There can be at most only one Condorcet winner, but there is one small drawback in the Condorcet system - it is possible that there may be no Condorcet winner. \InputFile Input for each test case will start with a single line containing two positive integers \textbf{b} \textbf{c}, where \textbf{b} indicates the number of ballots and \textbf{c} indicates the number of candidates. Candidates are considered numbered \textbf{0}, ..., \textbf{c-1}. Following this first line will be \textbf{b} lines containing \textbf{c} values each. Each of these lines represents one ballot and will contain the values \textbf{0}, ..., \textbf{c-1} in some permuted order. Values of \textbf{b} and \textbf{c} will lie in the ranges \textbf{1}...\textbf{500} and \textbf{1}...\textbf{2500}, respectively, and the line \textbf{0 0} will follow the last test case. \OutputFile For each test case output a single line containing either the candidate number of the Condorcet winner, or the phrase \textbf{No Condorcet winner} using the format given.
Time limit 5 seconds
Memory limit 64 MiB
Input example #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
Output example #1
Case 1: 1
Case 2: No Condorcet winner
Source 2011 East Central Regional Contest