Online MIPT programming contest | РУССКИЙ |
<PREV Problem: | NEXT> |
< |
---|
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 ...Here V is number of vertices (V < 10001), E is number of edges (E < 100001), (s_{i}, t_{i}) is i-th edge description. Vertices are denoted by numbers 0, 1, ..., V-1.s_{E} t_{E}
Output. The first line should contain the minimal number M of edges to add. Then M lines with their description should follow.
Input#14 3 0 1 1 2 1 3 |
Output#12 3 0 2 0 |
Input#26 5 0 2 1 2 2 3 3 4 4 5 |
Output#22 5 0 5 1 |
Author:
Well-known problem. Tests and description by Artem Voroztsov. Checker by Dmitry Korolev.
10 May 2006
© acm.mipt DevGroup The page was generated in 200ms |