MOWS - Madrids One Way Streets

no tags 

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 As and Bs, indicating that there is a one-way street from object As to Bs.

A blank line precedes each test case.

The sample input corresponds to the following graph:

Graph for sample input

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

hide comments
shiv2111: 2018-01-16 17:17:13

very easy scc...

Anne: 2016-10-11 10:51:41

Kosaraju!

Deepak : 2016-01-27 09:32:01

good question..learnt a hell lot of things..

Priyanjit Dey: 2015-07-12 10:51:57

why the answer is not hotel 2? i can visit all the places of interest from there. There are direct edges to the places of interest.

heatOn: 2014-06-30 22:47:47

WAs due to stupid mistakes :(


Added by:Jonas Wagner
Date:2009-10-14
Time limit:0.454s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 C++ 4.3.2 ERL NODEJS OBJC PERL6 SQLITE VB.NET