FPC24-023.European Election

The European presidential election of 2042 are coming up soon. The First Presidential Committee has devised the most objective and representative election method. Every candidate is individually compared to every other candidate. The winner of the election is going to be the one candidate who is preferred over all other candidates.

To facilitate this, on their ballot, each voter lists candidates in order of preference. From those rankings, the head-to-head preferences of each voter are inferred. Not all candidates have to be ranked by every voter – omitted candidates are considered to all be ranked last by the voter (with no preference between them). A candidate is better than another candidate if more people prefer that candidate over the other one. If a candidate is better than every other candidate, they win the election.

Consider the second sample input, where there are seven voters and three candidates. In the head-to-head battle between candidates $1$ and $2$, four voters prefer candidate $1$ and two voters prefer candidate $2$ (one voter is indifferent about both), so candidate $1$ wins that head-to-head match-up. Between candidates $1$ and $3$, four people prefer candidate $1$, and three people prefer candidate $3$, thus candidate $1$ is better. Therefore, candidate $1$ wins the election.

In case no candidate wins against all other candidates, then the results of the election are inconclusive – there is no winner. If, in a head-to-head battle, two candidates have the same number of preferences, then neither of them is considered better than the other. Thus, neither of them would be able to win the election.

Given the contents of each ballot, determine whether the election has a conclusive winner, and if so, who that winner is.