== include(page="template/taskheader" task_id="pamant") ==
Poveste şi cerinţă...
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~, ... , $C$~k~ astfel încât $P = C$~1~, $Q = C$~k~, şi oricare ar fi $1 ≤ 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.
h2. Cerinţă
Scrieţi un program care să identifice toate echipele formate conform regulilor de mai sus, precum şi care sunt copiii vulnerabili.
h2. Date de intrare
Fişierul de intrare $pamant.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $pamant.out$ ...
* 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.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 200.000$
* 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$.
* Se acordă $40%$ din punctaj pentru corectitudinea primelor două linii din fişierul de ieşire şi $60%$ pentru celelalte două linii.
* Pentru $30%$ din teste $N ≤ 1.000$.
h2. Exemplu
table(example). |_. pamant.in |_. pamant.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 10 7
1 2
2 8
4 6
3 5
3 10
5 10
5 7
| 4
1 3 4 9
2
2 5
|
h3. 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$.
== include(page="template/taskfooter" task_id="pamant") ==
