pamant

Pe pământul din apropierea localităţii Gheorgheni s-au întâlnit toţi copiii şi doresc organizarea unui joc mai deosebit. Copiii au fost numerotaţi de la $1$ la $N$ şi ştim care sunt prietenii fiecărui copil.

O echipă este un grup maximal de copii cu proprietatea că oricare ar fi copiii $P$ şi $Q$ din echipă, există un şir de copii $C_1, \dots , C_k$ astfel încât $P=C_1$, $Q=C_k$, şi oricare ar fi $1 \leq i < k$, $C_i$ este prieten cu $C_{i+1}$.

Fiecare echipă va primi un cod, egal cu cel mai mic număr de ordine al unui copil din echipa respectivă.

Dorim să aflăm care sunt copiii vulnerabili, adică acei copii care dacă ar fi eliminaţi ar duce la spargerea echipei sale în două sau mai multe echipe.

Cerinţă

Scrieţi un program care să identifice toate echipele formate conform regulilor de mai sus, precum şi care sunt copiii vulnerabili.

Date de intrare

Fişierul de intrare pamant.in conţine:

• pe prima linie două numere naturale $N$ şi $M$ reprezentând numărul de copii şi respectiv numărul relaţiilor de prietenie;
• următoarele $M$ linii conţin câte două numere naturale distincte $x$ şi $y$, cu semnificaţia că $x$ şi $y$ sunt numerele de ordine a doi copii în relaţie de prietenie.

Date de ieşire

• Prima linie a fişierului de ieşire pamant.out conţine o singură valoare naturală $A$, reprezentând numărul de echipe.
• A doua linie conţine $A$ numere naturale separate prin câte un spaţiu reprezentând codurile echipelor, în ordine crescătoare.
• A treia linie conţine o valoare naturală $B$ reprezentând numărul de copii vulnerabili.
• A patra linie conţine $B$ valori naturale, separate prin câte un spaţiu, reprezentând numerele de ordine, scrise în ordine crescătoare, ale copiilor vulnerabili.

Restricţii şi precizări

• $1 \leq N \leq 100\ 000$
• $1 \leq M \leq 200\ 000$
• Se acordă $40\%$ din punctaj pentru corectitudinea primelor două linii din fişierul de ieşire şi $60\%$ pentru celelalte două linii.
• Relaţiile de prietenie sunt reciproce: dacă $x$ este prieten cu $y$, atunci şi $y$ este prieten cu $x$.
• Dacă $x$ este prieten cu $y$ şi $y$ este prieten cu $z$ nu înseamnă că $x$ este prieten cu $z$.
• Pentru $30\%$ din teste $N \leq 1\ 000$.

Exemplu

pamant.in

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

pamant.out

4
1 3 4 9
2
2 5

Explicaţie

Există $4$ echipe şi anume:

• prima echipă: $(1,2,8)$
• a doua echipă: $(3,5,7,10)$
• a treia echipă: $(4,6)$
• a patra echipă: $(9)$

Există doi copii speciali şi anume $2$ şi $5$.