== include(page="template/taskheader" task_id="porumbei") ==
Într-un regat medieval sunt $N$ castele care comunică între ele prin intermediul porumbeilor voiajori. Un porumbel poate duce mesaje doar între două orașe și numai într-un sens (el știe doar să se întoarcă acasă, de unde trebuie adus manual înapoi). Regele cunoaște rutele care dispun porumbei.
Într-un regat medieval sunt $N$ castele care comunică între ele prin intermediul porumbeilor voiajori. Fiecare porumbel are un castel „casă” și, odată lăsat liber de la alt castel, nu știe decât să zboare acasă (porumbeii sunt aduși înapoi manual). Diverse perechi de castele au stabilit astfel de rute unidirecționale. Un castel $C[~0~]$ poate trimite mesaje către un castel $C[~k~]$ (unde $k$ > 0) dacă există un șir de castele $C[~1~]$, $C[~2~]$, ..., $C[~k-1~]$ astfel încât pentru fiecare pereche $(C[~i~]$, $C[~i+1~])$ să existe o rută de porumbei $(0 ≤ i < k)$.
Regele dorește ca regatul lui să fie _mobilizat_ în orice clipă împotriva unei eventuale agresiuni. El se declară mulțumit dacă, pentru orice pereche de castele A și B, A poate trimite mesaje către B sau B către A (sau ambele). Cunoscând numărul de castele și rutele de porumbei, ajutați-l pe rege să decidă dacă regatul este mobilizat.
h2. Date de intrare
Fișierul de intrare $porumbei.in$ ...
Fișierul de intrare $porumbei.in$ conține pe prima linie două numere $N M$, despărțite printr-un spațiu. $N$ este numărul de castele, iar $M$ este numărul de rute. Pe următoarele $M$ linii se află câte o pereche de numere distincte $x y$ cu semnificația că există o rută unidirecțională de porumbei de la castelul $x$ la castelul [$y$].
h2. Date de ieșire
În fișierul de ieșire $porumbei.out$ ...
În fișierul de ieșire $porumbei.out$ se va tipări un singur mesaj, $DA$ sau [$NU$], după cum regatul este mobilizat sau nu.
h2. Restricții
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 300.000$
* Castelele sunt numerotate de la 1 la [$N$].
* Toate rutele sunt distincte.
h2. Exemplu
table(example).
|_. porumbei.in |_. porumbei.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 5 5
1 2
2 3
3 1
2 4
5 3
| DA
|
| 5 5
1 2
2 3
3 1
2 4
3 5
| NU
|
h3. Explicație
...
În al doilea exemplu, castelele 4 și 5 nu pot comunica în nicio direcție.
== include(page="template/taskfooter" task_id="porumbei") ==
