As you know, PolyProg wants to send EPFL's best coders to Madrid. Now an important question that arises is where they should stay. Apart from being a cheap place, it should also be close to the contest location and the main tourist spots.

Now the problem is that there are mostly one-way streets in Madrid (actually there aren't, but this problem is so nice that we wanted to include it in this contest nevertheless). We would like to get to the contest and back to the hotel without breaking any traffic rules... can you help finding a hotel that allows to do so?

To be precice, we'd like to find a hotel that allows us to go to each place of interest and back again. If that's not possible, we'd like a hotel that allows us to travel to and from as many places of interest as possible. If the same number of places can be accessed from several hotels, you should choose the hotel with the smallest id.

Input

The first line of the input contains 1 ≤ N ≤ 10, the number of test cases. Then follow three numbers 1 ≤ H ≤ 1000, 1 ≤ P ≤ 100'000 and 1 ≤ S ≤ 1'000'000 denoting the number of hotels, places of interest and streets, respectively.

In order to simplify things, we just represent hotels and places of interests as numbers: Hotels are numbered from 1 to H, whereas places are numbered from 1001 to 1000 + P.

Each of the following S lines contains two numbers A_s and B_s, indicating that there is a one-way street from object A_s to B_s.

A blank line precedes each test case.

The sample input corresponds to the following graph:

Output

For each testcase, print the id of the best hotel followed by the number of places of interest accessible from this hotel (and vice versa) on a line.

Example

Input:
1

2 4 10
1 1001
2 1001
2 1002
2 1003
2 1004
1001 1002
1002 1
1002 1003
1004 2
1004 1001

Output:
1 2