Transferable Voting

The transferable-vote system elects a single winner and requires that the winner hold an absolute majority of the valid ballots, even when there are more than two candidates. To make this possible, every voter ranks all of the candidates in order of preference. If there are $c$ candidates for the position, each ballot lists $c$ choices: a first choice, a second choice, and so on down to the $c$-th choice.

The candidates are numbered $1$ through $c$. A ballot is invalid (a "bad ballot") if its $c$ numbers are not all distinct — the same candidate may not be listed twice — or if any number falls outside the range $1$ to $c$. Invalid ballots are discarded, but they are counted and reported.

Let $V$ be the number of valid ballots. A candidate is elected as soon as they hold more than half of the valid ballots, that is at least $\lfloor V/2 \rfloor + 1$ votes.

The winner is found in rounds:

1. Give each valid ballot to its highest-ranked candidate who has not yet been eliminated.
2. If some candidate has at least $\lfloor V/2 \rfloor + 1$ votes, that candidate is elected.
3. Otherwise, if every remaining candidate has the same number of votes, they are all tied — report all of them.
4. Otherwise, eliminate every candidate tied for the fewest votes, then repeat from step 1.

Because each valid ballot ranks all $c$ candidates, an eliminated candidate's ballots always flow to the next-ranked candidate who is still in the running.

For example, consider a small election with 12 voters and 3 candidates. Their ballots are shown in Table A.

          Table A                Table B
-----------------------------    -------
Voter  First   Second  Third
       Choice  Choice  Choice
  1      1       2       4
  2      1       3       2       1  3  2
  3      3       2       1       3  2  1
  4      3       2       1       3  2  1
  5      1       2       3       1  2  3
  6      2       3       1       3  1
  7      3       2       1       3  2  1
  8      3       1       1
  9      3       2       1       3  2  1
 10      1       2       3       1  2  3
 11      1       3       2       1  3  2
 12      2       3       1       3  1

Voters 1 and 8 cast invalid ballots (voter 1 lists candidate 4, which does not exist; voter 8 lists candidate 1 twice), so they are not counted. That leaves 10 valid ballots, so winning requires at least 6 votes. Candidates 1 and 3 each have 4 first-choice votes and candidate 2 has 2, so no one has a majority. Candidate 2 has the fewest votes and is eliminated. The two ballots that ranked candidate 2 first now advance to their next surviving choice (Table B), giving candidate 3 two more votes for a total of 6 — enough to be elected. (Had voter 12 instead cast "2 1 3", candidates 1 and 3 would each have finished with 5 votes and the election would have been a tie.)

The input contains one or more elections. Each election begins with a line holding two integers, the number of candidates $c$ and the number of voters $n$ ($1 \le c \le 5$; there are at most 100 voters). The next $n$ lines each describe one ballot as $c$ whitespace-separated non-negative integers, listing that voter's choices from first to last.

The input ends with a line containing two zeros (0 0), which is not part of any election.

For each election, print the result in the following format, and print the elections one after another with no blank line between them:

• A line Election #k, where $k$ is the election's position in the input (the first election is #1).
• If the election had any invalid ballots, a line b bad ballot(s) (indented by three spaces), where $b$ is the number of invalid ballots. Omit this line when there are none.
• The result, indented by three spaces:
  • Candidate w is elected. if candidate $w$ wins, or
  • The following candidates are tied: followed by the numbers of the tied candidates in increasing order, with a space before each number and a space after the last one.