Un graf neorientat se numeşte biconex dacă este conex şi nu conţine puncte de articulaţie.

Un punct de articulaţie este un nod care prin ştergerea sa şi a muchiilor incidente cu el implică pierderea conexităţii.

O componentă biconexă a unui graf neorientat conex reprezintă un subgraf maximal biconex.

Se numeşte muchie critică într-un graf neorientat conex o muchie care prin eliminarea ei duce la pierderea conexităţii grafului.

Cerința

Dându-se un graf neorientat conex, sa se găsească:

1. Componentele biconexe;
2. Punctele de articulaţie;
3. Muchiile critice.

Date de intrare

Fișierul de intrare componentebiconexe.in va conţine pe prima linie un număr p, care poate lua valorile 1, 2 sau 3. Pe a doua linie se află n si m (numărul de noduri, respectiv numărul de muchii ale grafului dat). Pe următoarele m linii se află câte o pereche de numere a şi b cu semnificaţia ca există muchie între nodurile a şi b.

Date de ieșire

Fișierul de ieșire componentebiconexe.out va conține răspunsul la una dintre cerinţe astfel:

Dacă p este 1: pe prima linie se va afişa numărul de componente biconexe (nr). Pe următoarele nr linii se va afişa câte o componenta biconexă astfel: numărul de noduri din componenta biconexă urmat de nodurile din această componentă, toate separate prin spaţiu.

Dacă p este 2: pe prima linie se va afişa numărul de puncte de articulaţie. Pe a doua linie se vor afişa separate prin spaţiu toate punctele de articulaţie.

Dacă p este 3: pe prima linie se va afişa numărul de muchii critice, apoi pe câte o linie vor fi afişate muchiile critice.

Restricții și precizări

• 3 ≤ n ≤ 100.000
• 3 ≤ m ≤ 200.000
• Componentele biconexe, nodurile dintr-o componentă biconexă, punctele de articulaţie și muchiile critice se pot afişa în orice ordine.
• În fişierul de intrare nu va exista aceeaşi muchie de mai multe ori sau muchii de la un nod la el însuşi.

Exemplul 1

componentebiconexe.in

1
6 6
1 2
2 3
1 4
4 5
2 5
3 6

componentebiconexe.out

3
4 1 2 5 4
2 2 3
2 3 6

Exemplul 2

componentebiconexe.in

2
6 6
1 2
2 3
1 4
4 5
2 5
3 6

componentebiconexe.out

2
2 3

Exemplul 3

componentebiconexe.in

3
6 6
1 2
2 3
1 4
4 5
2 5
3 6

componentebiconexe.out

2
2 3
6 3