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 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.
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:
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.
2 4 10
very easy scc...
good question..learnt a hell lot of things..
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.
WAs due to stupid mistakes :(