BAD - Badminton Tournament - Easy

In a badminton tournament, each of n players play all the other n - 1 players. Each game results in either a win, or a loss. Players then write down the names of those whom they defeated (say list 1) and also of those who they (players of list 1) defeated. For example, if A beats B and B beats C, then A writes the names of both B and C.

Consider a game between A, B, C, D, E, F, G where A defeats B, C; B defeats E; C defeats F. Then A's list will have (B, C, E, F) and will not include G.

Note: Say A defeats B, B defeats C and C defeats D. D is not necessarily present in A's list, a player's list contains players of list1 and players defeated by those in list1 (immediate win).

In this problem, we represent players by integers from 1 to n (Both inclusive.)

Input

First line of input contains an integer t (number of test cases), each test case starts with an integer n followed by nc2 (i.e. n * (n - 1) / 2) lines (results of all matches) each containing two integers a, b separated by a space which means a defeated b.

Output

Print a line for each test case containing two space separated integers p, q where p is the player with maximum possible number of players in his list and q is that number (maximum possible number of players in a list).

In case there are many players with maximum number of players in their list, print minimum of such possibilities of p.

Constraints

t <= 50, n <= 250, 1 <= a, b <= n

Example

Input:
1
3
1 2
2 3
3 1

Output:
1 2

My best: 0.53s with PyPy and 1.50s with Python 2.7.9. Good Luck! :)


Added by:Vamsi Krishna Avula
Date:2015-01-13
Time limit:0.5s-2s
Source limit:4096B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU

hide comments
2017-02-03 16:57:56
Easy problem , brute force works.........
2017-02-03 14:55:22
don't try the toolkit..that's wrong..
2015-11-17 14:08:47 Rishav Goyal
what the hell. in__buitin_popcount does not work for long long int.
2015-09-21 13:59:49
I did not understand what you mean to say in note. D is not necessarily included in A's list. So, i want to know in which case we will include D , and in which case, we will exclude D.
And in sample test case. List of every ;articipant will have 2 names, so, should p be equal to 3(as per i am able to understand the language of the question)?
Any help will be appreciated.



Last edit: 2015-09-21 14:06:12
2015-06-02 21:20:14 Ayon Das
Awesome problem!! AC in one go for .3 points :D
2015-05-21 14:28:54 Maroof
4
1 2
3 1
4 1
2 3
4 2
3 4

output: 2 3
2015-02-17 17:41:56 Stefan Burgic
can you give us more test cases? :)

re(vamsi): It should be easy to build some test cases yourself(by hand). In case you didn't understand the problem statement, I'll be happy to help.

Last edit: 2015-02-25 17:23:02
2015-02-17 17:41:56 Stefan Burgic
A beats B, B beats C, C beats A..

A writes B,C
B writes C,A
C writes A,B

Is it okay or not?

re(vamsi): yes, it is fine


Last edit: 2015-02-25 17:24:08
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.