A tennis tournament

2

3 votes
Graphs, Graph Theory, Algorithms, Graph, Depth First Search, C++
Problem

There was a tennis tournament held recently and Sylvie was following the matches when she noticed something odd. She knows for a fact that in this tournament someone will win against someone else if and only if they are better than them and there is no draw in the games.

She observed that some winning loops were formed in the tournament, meaning that if among players to , for each from to , had won against , then the player had won against which should be impossible. Therefore, she suspected that there was some doping involved.
She wanted to report it to the tournament organizer so they can act accordingly but to prove her point she wanted to give them an example. She decided to provide them with the smallest loop possible so verifying it would not be so hard. Now, you have to help her find the smallest loop.

In other words, there is a directed graph and you have to find the smallest cycle possible.

Note: The graph does not have any self-loops but multiple edges are allowed.

Input format

  • The first line contains integers and denoting the number of players and the number of matches respectively.
  • Each of the next lines contains two integers , which means there was a match between and that had won against .

Output format

  • In the first line of output, you should print a single integer represents the length of the smallest winning loop in the tournament.
  • In the next lines, print two integers and in each line which represents one of the matches in the winning loop that you have found and had won against in that match (an edge of the graph).

Note: If there is no winning loop in the tournament (cycle in the graph), then print in the only line of output.

Constraints

Scoring
If there is no cycle, your answer is considered as in the scoring.

Sample Input
7 9
1 2
2 3
3 4
4 5
5 6
6 7
7 4
4 1
1 7
Sample Output
4
4 5
5 6
6 7
7 4
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In this sample, edges (4, 5), (5, 6), (6, 7), (7, 4) construct a cycle of length 4. However, this is not the minimum cycle that exists, because edges (4, 1), (7, 4), (1, 7) form a cycle of length 3.

Editor Image

?