Rezolvare PBinfo #3365

Se dă un digraf (graf orientat) cu n noduri numerotate de la 1 la n. Graful componentelor tare conexe se obține astfel: se construiesc componentele tare conexe, apoi fiecare astfel de componentă devine nod în noul graf. Apoi din lista inițială de arce se păstrează în noul graf numai arcele care au extremitățile în componente tare conexe diferite. Dacă există mai multe arce între aceleași două noduri în noul digraf, se păstrează toate.

Componentele tare conexe se vor construi astfel: prima componentă este cea care conține nodul 1, a doua componentă este cea care conține cel mai mic nod care nu se află în prima componentă ș.a.m.d.

Lista de adiacență asociată unui nod i din digraful componentelor tare conexe conține toate nodurile j cu proprietatea că există arcul (i, j).

Cerința

Să se afișeze listele de adiacență asociate noului digraf.

Date de intrare

Programul citește de la tastatură numerele n și m, iar apoi m perechi de forma i j cu semnificația: există arcul (i,j) în digraf.

Date de ieșire

Programul va afișa pe ecran nrC linii, unde nrC este numărul componentelor tari conexe, adică numărul de noduri din noul graf. Pe fiecare din următoarele i linii se vor afișa, în ordine crescătoare adiacenții externi ai nodului i din noul digraf. Dacă există k arce (i, j) atunci în lista de adiacență a lui i nodul j va apărea de k ori, deci se va afișa de k ori. Dacă un nod k din noul digraf are gradul exterior 0, se va afișa doar un 0.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• 1 ≤ m ≤ 200.000
• în toate testele, digraful are cel puțin două componente tari conexe

Exemplu:

Intrare

8 10
1 2
2 3
3 1
4 5
5 6
6 7
7 4
6 4
4 1
4 8

Ieșire

0
1 3
0

Explicație

Graful are 8 noduri și 10 arce:

Prima componentă conexă este formată cu nodurile 1 2 3, a doua cu nodurile 4 5 6 7, iar a treia este formată din nodul 8. Din digraful inițial se păstrează numai arcele (4,1) și (4,8). Graful asociat componentelor tare conexe este: