{"raw_statement":[{"iden":"statement","content":"Finally, it is time to vote for a new president and you are really excited about that. You know that the final results may take weeks to be announced, while you can't really wait to see the results.\n\nSomehow you managed to get the preferences list for every voter (we don't care how you managed to get this piece of information!). Each voter sorted out all candidates starting by his most preferred candidate and ending with his least preferred one. When voting, a voter votes for the candidate who comes first in his preferences list. For example, if there are 5 candidates (numbered 1 to 5), and the preferences list for one voter is [3, 2, 5, 1, 4] and the current competing candidates in the voting process are candidates 2 and 4, the voter will vote for candidate number 2.\n\nHere are the rules for the election process: \n\nGiven the preferences lists, you need to write a program to figure out which candidate will win and in which round.\n\nYour program will be tested on one or more test cases. The first line of the input will be a single integer *T*, the number of test cases (1  ≤  *T*  ≤  100). Followed by the test cases, the first line of a test case contains two integers *C* and *V* separated by a single space. *C* and *V* (1  ≤  *C*, *V*  ≤  100) represent the number of candidates and voters respectively, followed by *V* lines each line contains *C* integers separated by a single space, representing the preferences list for a single voter (the first is his most preferable candidate while the last is his least preferable one). Each integer from 1 to *C* will appear exactly once in each line.\n\nFor each test case, print on a single line two integers separated by a single space. The first integer is the ID of the winner candidate (a number from 1 to *C*), the second integer is either 1 or 2 indicating whether this candidate will win in the first round or the second one respectively.\n\n"},{"iden":"input","content":"Your program will be tested on one or more test cases. The first line of the input will be a single integer *T*, the number of test cases (1  ≤  *T*  ≤  100). Followed by the test cases, the first line of a test case contains two integers *C* and *V* separated by a single space. *C* and *V* (1  ≤  *C*, *V*  ≤  100) represent the number of candidates and voters respectively, followed by *V* lines each line contains *C* integers separated by a single space, representing the preferences list for a single voter (the first is his most preferable candidate while the last is his least preferable one). Each integer from 1 to *C* will appear exactly once in each line."},{"iden":"output","content":"For each test case, print on a single line two integers separated by a single space. The first integer is the ID of the winner candidate (a number from 1 to *C*), the second integer is either 1 or 2 indicating whether this candidate will win in the first round or the second one respectively."},{"iden":"examples","content":"Input22 32 11 22 13 51 2 31 2 32 1 32 3 13 2 1Output2 12 2"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ C \\in \\mathbb{Z} $ be the number of candidates, $ V \\in \\mathbb{Z} $ the number of voters.  \n- Let $ P = (P_1, P_2, \\dots, P_V) $ be the profile of preference lists, where each $ P_j = (p_{j,1}, p_{j,2}, \\dots, p_{j,C}) $ is a permutation of $ \\{1, 2, \\dots, C\\} $, representing voter $ j $’s ranked preferences.\n\n**Constraints**  \n1. $ 1 \\le T \\le 100 $  \n2. For each test case:  \n   - $ 1 \\le C, V \\le 100 $  \n   - Each $ P_j $ is a permutation of $ \\{1, 2, \\dots, C\\} $\n\n**Objective**  \nSimulate a two-round voting system:  \n- **Round 1**: Each voter votes for their most preferred candidate (i.e., $ p_{j,1} $). Let $ f(c) $ be the number of first-choice votes for candidate $ c $.  \n  - If $ \\exists c^* $ such that $ f(c^*) > \\frac{V}{2} $, then $ c^* $ wins in **round 1**.  \n- **Round 2**: If no candidate has a majority in Round 1, eliminate all candidates except the top two by first-choice vote count. Each voter then votes for the candidate among the two remaining who appears earliest in their preference list. The candidate with the most votes in this round wins in **round 2**.  \n\nOutput: $ (w, r) $, where $ w \\in \\{1, \\dots, C\\} $ is the winning candidate and $ r \\in \\{1, 2\\} $ is the round of victory.","simple_statement":"You are given C candidates and V voters. Each voter ranks all candidates from most to least preferred. In the first round, everyone votes for their top choice. If any candidate gets more than half the votes, they win in round 1. Otherwise, the top two candidates by first-round votes advance to round 2. In round 2, each voter votes for whichever of the two is higher on their list. Output the winner’s ID and the round they won (1 or 2).","has_page_source":false}