== include(page="template/taskheader" task_id="matroid") ==
Poveste și cerință...
Grădina zoologică din satul Matroid a rămas fără bani. Directorul grădinii, pentru a face economie la hrană, s-a gândit să hrănească unele animale cu altele, până când în final rămâne cu un singur animal supraviețuitor. El primește o listă cu dieta animalelor și știe dacă un animal poate sau nu să mănânce alt animal. Ajutați-l pe director să afle care dintre animale ar putea fi supraviețuitorul final.
Grădina zoologică are $N$ animale distincte. Directorul nu se pricepe la taxonomie, așa încât nu operează cu numele animalelor, ci cu numerele lor de ordine, cuprinse între 1 și [$N$].
h2. Date de intrare
Fișierul de intrare $matroid.in$ ...
Fișierul de intrare $matroid.in$ conține pe prima linie două numere $N M$, unde $N$ este numărul de animale, iar $M$ este lungimea listei de informații despre dietă. Pe următoarele $M$ linii se află câte o pereche de numere $x y$, cu semnificația că animalul $x$ se poate hrăni cu animalul [$y$].
h2. Date de ieșire
În fișierul de ieșire $matroid.out$ ...
În fișierul de ieșire $matroid.out$ se va scrie, pe prima linie, numărul de animale care ar putea fi supraviețuitorul final. Pe următoarele linii se vor scrie numerele acestor animale, în ordine crescătoare, câte unul pe linie.
h2. Restricții
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 300.000$
h2. Exemplu
table(example).
|_. matroid.in |_. matroid.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 4 5
1 2
1 3
3 4
2 4
3 1
| 2
1
3
|
| 4 2
1 2
3 4
| 0
|
h3. Explicație
...
Pentru primul exemplu, animalul 1 poate fi supraviețuitor: 2 îl mănâncă pe 4, 1 pe 2, 1 pe 3. De asemenea, animalul 3 poate fi supraviețuitor: 3 îl mănâncă pe 4, 1 pe 2, 3 pe 1.
În al doilea exemplu, grădina zoologică nu poate fi redusă la un singur animal.
== include(page="template/taskfooter" task_id="matroid") ==
