Fişierul intrare/ieşire:porumbei.in, porumbei.outSursăCormen
AutorCatalin FrancuAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.5 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.inporumbei.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici