MOWS  Madrids One Way Streets
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 oneway 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 oneway 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
hide comments
shiv2111:
20180116 17:17:13
very easy scc... 

Anne:
20161011 10:51:41
Kosaraju! 

Deepak :
20160127 09:32:01
good question..learnt a hell lot of things.. 

Priyanjit Dey:
20150712 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:
20140630 22:47:47
WAs due to stupid mistakes :( 
Added by:  Jonas Wagner 
Date:  20091014 
Time limit:  1s 
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 