<PREV Problem:
NEXT>
Solved by 51 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Upgrading to strongly connected graph

Time limit = 5 second(s)

You are given directed graph. Add minimal number of edges to make it strongly connected.

Graph is strongly connected iff for any vertices A and B there are paths from A to B, and from B to A.

Input. Input format is

V E
s1 t1
s2 t2
...

sE tE

Here V is number of vertices (V < 10001), E is number of edges (E < 100001), (si, ti) is i-th edge description. Vertices are denoted by numbers 0, 1, ..., V-1.

Output. The first line should contain the minimal number M of edges to add. Then M lines with their description should follow.

Input#1
4 3
0 1
1 2
1 3
Output#1
2
3 0
2 0

Input#2
6 5
0 2
1 2
2 3
3 4
4 5
Output#2
2
5 0
5 1

Author:
Well-known problem. Tests and description by Artem Voroztsov. Checker by Dmitry Korolev.
10 May 2006

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 54.224.164.166