32588번 - 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.

입력

The input consists of:

• One line with integers $n$ and $k$ (1ドル \leq n \leq 2000,ドル 1ドル \leq k \leq 200$), denoting the number of ballots cast and the number of candidates.

• \item $n$ lines, one for each ballot.

  Each line starts with an integer $v$ (0ドル \leq v \leq 200$), the number of preferences on this ballot.

  The remainder of this line has $v$ integers $p$ (1ドル \leq p \leq k$), denoting the preferences of this voter -- the first integer is the number of the voter's first preference candidate, the second integer is their second preference, and so on.

  All the candidates that are unranked (i.e. not mentioned in the ballot) are considered to be all ranked last (i.e.\ tied with each other).

출력

If the election has a conclusive winner, output the number of the candidate who wins the election. Otherwise, output "impossible".

제한

힌트