PRESIDEN - The new President

no tags 

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.

Somehow 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.

Here are the rules for the election process:

  1. There are C candidates (numbered from 1 to C), and V voters (V is always an odd number).
  2. The election process consists of up to 2 rounds. All candidates compete in the the first round. If a candidate receives more than 50% of the votes, he wins, otherwise another round takes place, in which only the top 2 candidates compete for the presidency. The candidate who receives more votes than his opponent wins and becomes the new president.
  3. You can safely assume that the given preferences will never cause a situation in which the second and the third candidates from the first round receive the same number of votes.
  4. The voters' preferences are the same in both rounds, and each voter must vote exactly once in each round for a currently competing candidate according to his preferences.

Given the preferences lists, you need to write a program to figure out which candidate will win and in which round.

Input

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 ≤ CV ≤ 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.

Output

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 cither 1 or 2 indicating whether this candidate will win in the first round or the second one respectively.

Example

Input:
2
2 3
2 1
1 2
2 1
3 5
1 2 3
1 2 3
2 1 3
2 3 1
3 2 1

Output:
2 1
2 2

hide comments
Anuj_LuckFove!: 2013-02-10 10:55:28

AC ;)

Last edit: 2013-02-12 16:32:40
MR. BEAN : 2013-01-17 21:12:17

@bigBOSS read the 3rd point , u can assume that such a case will not come...

Last edit: 2013-01-17 21:12:37
bigBOSS: 2013-01-17 18:43:04

Is this a fair test case...
3 3
1 3 2
3 1 2
2 3 1
and if yes....should the answer be 3 1 or 3 2?

By Kawmia institutes problems setters :
it isn't a fair case since there is more than 1 candidate having the same number of votes

Last edit: 2013-01-17 22:23:23

Added by:Kawmia Institutes
Date:2013-01-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 BF CLPS CLOJURE LISP sbcl LISP clisp D ERL FORTRAN ICON ICK LUA NEM NODEJS OCAML PRLG-swi SCM guile SCM qobi SED ST TCL WHITESPACE
Resource:ACM ICPC 2012