Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Election
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 948Accepted: 445

Description

Given the voting preferences of a population of M people, you are to determine the winner of an election among N candidates, numbered 1, …, N. For this problem, the M people are partitioned into G “groups” where all members within a group have the same voting preferences. The candidate preferences for a group are specified by listing candidates from most preferred to least preferred. Election results are determined by an instant-runoff voting procedure.

In this method, the first choices of the M people in the population are counted and the least popular candidate is eliminated. In the event of a tie, the highest-numbered candidate is eliminated. Then, the eliminated candidate is removed from the preference list of all M individuals in the population, and again the least popular candidate is eliminated. This process repeats until only a single candidate is left.

Input

The input test file will contain multiple test cases. Each input test case begins with a single line containing the integers G and N where 2 ≤ N ≤ 5 and 1 ≤ G ≤ 20. The next G lines are of the format “Mi ai1 ai2aiN” where 1 ≤ Mi ≤ 20 and ai1, …, aiN is a permutation of the integers 1, …, N. Mi is the number of individuals in the ith group, and ai1, …, aiN is the ordering of the N candidates from most preferred to least preferred for the ith group. The end-of-file is marked by a test case with G = N = 0 and should not be processed.

Output

For each input case, the program should print the winner of the election on a single line.

Sample Input

3 4
10 1 4 2 3
15 3 2 1 4
12 4 3 2 1
3 2
10 1 2
10 1 2
20 2 1
0 0

Sample Output

4
1

Source

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

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator