weddingcity

Problem Description

Rar is hosting his wedding in his hometown, Goldmill. Eager to plan his wedding all the way down to the finest detail, Rar recreates a map of Goldmill, modelling it as a graph with N road intersections and E roads connecting them. Each road is a one-way road, with road i allowing cars to travel from intersection A_i to B_i. It is guaranteed that no two roads will have the same A_i and B_i, and a road will not connect a city to itself (A_i ≠ B_i).

While drawing the map, Rar realises a HUGE problem! Some of the guests he are inviting are not of intelligence, and might get stuck in a dead end. If too many guests get stuck, they won't be able to make it to Rar's wedding and all the empty seats would make Jacq the Dinosaur very unhappy.

Rar wants to make Goldmill dead-end free, meaning it must be possible to travel from any road intersection in Goldmill to any other road intersection using a subset of the roads that exist in Goldmill. He can do this by adding some number of new one-way roads, each allowing travel from one specified road intersection to another.

Help Rar find the minimum number of new roads he needs to construct to accomplish this goal, and provide him with a possible set of roads he may wish to construct.

Input

The first line of input will contain two integers, N and E.

The next E lines of input will contain two integers each, A_i and B_i.

Output

The first line of output should contain one integer, the minimum number of new roads Rar needs to construct, X.

The next X lines of input will contain two integers each, A_i and B_i for each new road constructed.

Limits

For all subtasks:

• 2 ≤ N ≤ 10⁵
• 1 ≤ E ≤ 10⁵
• 0 ≤ A_i, B_i < N
• A_i ≠ B_i
• (A_i, B_i) ≠ (A_j, B_j)

Subtask 1 (5%): 2 ≤ N ≤ 10, 1 ≤ E ≤ 10

Subtask 2 (16%): 2 ≤ N ≤ 1000, 1 ≤ E ≤ 1000.

Subtask 3 (17%): A_i < B_i, A_i ≠ B_j, for all 0 ≤ i, j < E.

Subtask 4 (30%): A_i < B_i for all 0 ≤ i < E.

Subtask 5 (7%): Your answer will be considered correct as long as the value of X provided is correct.

Subtask 6 (25%): No additional constraints.

Subtask 7 (0%): Sample.

Sample Input 1

6 5
0 1
1 3
3 0
1 2
4 0

Sample Output 1

2
2 5
5 4

Sample Input 2

4 4
0 1
1 2
2 3
3 0

Sample Output 2

0