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 C1, ... , Ck astfel încât P=C1, Q=Ck, şi oricare ar fi 1≤i<k, Ci este prieten cu Ci+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
• 1 ≤ N ≤ 100.000
• 1 ≤ M ≤ 200000
• 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.
Exemple
pamant.in
pamant.out
Explicaţii
10 7
1 2
2 8
4 6
3 5
3 10
5 10
5 7
4
1 3 4 9
2
2 5
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.