Fișierul intrare/ieșire | porumbei.in, porumbei.out | Sursă | Cormen |
---|---|---|---|
Autor | Cătălin Frâncu | Adăugată de | Cătălin Frâncu • Catalin.Francu |
Timp de execuție pe test | 0.5 sec | Limită de memorie | 8192 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Porumbei (clasele 11-12)
Î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 C0 poate trimite mesaje către un castel Ck (unde k > 0) dacă există un șir de castele C1, C2, ..., Ck-1 astfel încât pentru fiecare pereche (Ci, Ci+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.
Date de intrare
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.
Date de ieșire
Î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.
Restricții
- 1 ≤ N ≤ 100.000
- 1 ≤ M ≤ 300.000
- Castelele sunt numerotate de la 1 la N.
- Toate rutele sunt distincte.
Exemplu
porumbei.in | porumbei.out |
---|---|
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 |
Explicație
În al doilea exemplu, castelele 4 și 5 nu pot comunica în nicio direcție.