Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

Language:
Helping Florida
 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 435 Accepted: 96

Description

While Florida's difficulties electing presidents are well known, a lesser known problem is electing committee chairs within the state's House of Delegates. The process used is a runoff election,where each committee member submits a ballot with a ranked list of other members for the position of chair. Unfortunately, those responsible for tabulating the votes keep losing track of which ballots still have countable votes, and so no one trusts the results.
Each committee member submits a ballot. Each ballot contains a ranked list of votes. Tabulating the votes proceeds in rounds. For the first round, the first vote on each ballot is counted. If any candidate has more than half of the votes, they win.
After each round, the candidate receiving the fewest votes (or candidates, in the case of a tie for fewest votes) is eliminated. Votes are then re-tabulated with each ballot's highest vote for a remaining candidate being counted. If all of the candidates voted for on a ballot are eliminated,then that ballot is considered "non-viable," and it is no longer counted toward the total number of ballots when calculating majority.
The process is repeated until you have a single winner, or a tie between the remaining candidates.The rules of the election guarantee you will have a tie or a winner.

Input

For each dataset:
Line 1 < candidates > < ballots >
The number of candidates receiving votes
The number of ballots, b
b Lines One line per ballot. For each ballot, the names of the candidates are listed in order of preference. A candidate name is a string with no whitespace in it. A ballot may not contain votes for all candidates. No candidate will be repeated on a single ballot.
After the last dataset, a line of
0 0
will indicate the end of the input.

Output

For each dataset a single line is output:
For a winner:
< candidate > won
For a tie:
it is a tie between < candidate > and < candidate > [ and < candidate > [...]]
Each candidate name is separated by "and". They may be printed in increasing order.

Sample Input

```3 9
Buchanan Bush
Buchanan Bush
Buchanan Gore
Gore Bush
Gore Bush
Gore Bush
Gore Bush
Bush Buchanan
Bush Buchanan
0 0```

Sample Output

`Buchanan won`

Source

[Submit]   [Go Back]   [Status]   [Discuss]