Solved by 50 users: wojtekt, Anju7a, zmy, Huang_SR, gawry, fpascal145, old1, JohnJones_001, mikleb, Smitty, marek.cygan, mishik, dan, ignat, Rizvanov, tourist, Cheryl, davidsun, zloy_mipt, WsemirZ, mage, DAV, mazahaka, RAVEman, pmnox, Ravent, defrager, UdH-WiNGeR, piter, akopich, ZhanibekDATBAEV, Dest, LiuChenheng, igor.a.ehrlich, Krot, Madiyar_Tktl, tron, Purutchik, regmar, Avitella, shkiper, Ekaterina_Pogodina, Ekaterina_, sofiapotapova, NuM, mtretyak, tulindanil, daniltuiln, dzhavaharnal, danicheeeeeeeeee.
` <  <  <  <  <  <  <  <  <  < `

## 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

 © acm.mipt DevGroupThe page was generated in 190ms