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 Ai to Bi. It is guaranteed that no two roads will have the same Ai and Bi, and a road will not connect a city to itself (AiBi).

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, Ai and Bi.

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, Ai and Bi for each new road constructed.

Limits

For all subtasks:

  • 2 ≤ N ≤ 105
  • 1 ≤ E ≤ 105
  • 0 ≤ Ai, Bi < N
  • Ai ≠ Bi
  • (Ai, Bi) ≠ (Aj, Bj)

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

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

Subtask 3 (17%): Ai < Bi, Ai ≠ Bj, for all 0 ≤ i, j < E.

Subtask 4 (30%): Ai < Bi 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

Submitting .cpp to 'weddingcity'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 1 Seconds
Memory Limit: 1024MB
No. of ACs: 2
Your best score: 0
Source: IOI Sparring 2018 SGP

Subtask Score
1 5
2 16
3 17
4 30
5 7
6 25
7 0