In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].

If you are familiar with IRC chat, the support team is also reachable on PIRC network (`irc.pirc.pl`

) in `#szkopul`

channel. If you are not, just use email.

Please do not ask us things like "how to solve task XYZ?".

Please remember that the support team has to sleep sometimes or go to work in real life.

<Submit a solution> [0/100]**Task statistics**

Number of users: 187

Number of users with 100 points: 107

Average result: 74.7861

# Rally

### Memory limit: 128 MB

## Input

## Output

## Example

Number of users: 187

Number of users with 100 points: 107

Average result: 74.7861

An annual bicycle rally will soon begin in Byteburg. The bikers of Byteburg are natural long distance cyclists. Local representatives of motorcyclists, long feuding the cyclists, have decided to sabotage the event.

There are intersections in Byteburg, connected with one way streets. Strangely enough, there are no cycles in the street network - if one can ride from intersection to intersection , then it is definitely impossible to get from to .

The rally's route will lead through Byteburg's streets. The motorcyclists plan to ride their blazing machines in the early morning of the rally day to one intersection and completely block it. The cyclists' association will then of course determine an alternative route but it could happen that this new route will be relatively short, and the cyclists will thus be unable to exhibit their remarkable endurance. Clearly, this is the motorcyclists' plan - they intend to block such an intersection that the longest route that does not pass through it is as short as possible.

In the first line of the standard input, there are two integers, and (, ), separated by a single space, that specify the number of intersections and streets in Byteburg. The intersections are numbered from to . The lines that follow describe the street network: in the -th of these lines, there are two integers, , (, ), separated by a single space, that signify that there is a one way street from the intersection no. to the one no. .

In tests worth 33% of total score, for every street .

The first and only line of the standard output should contain two integers separated by a single space. The first of these should be the number of the intersection that the motorcyclists should block, and the second - the maximum number of streets that the cyclists can then ride along in their rally. If there are many solutions, your program can choose one of them arbitrarily.

For the input data:

6 5 1 3 1 4 3 6 3 4 4 5

the correct result is:

1 2

**Sample grading tests:**

`1ocen:`, , a path, best to be blocked in the middle;`2ocen:`, , for every pair of intersections, there is a street from the one with lower number to the one with higher number;`3ocen:`, , the streets from intersection go to (for ) and (for ).

*Task author: Bartosz Tarnawski.*