Fișierul intrare/ieșire porumbei.in, porumbei.out Sursă Cormen
Autor Cătălin Frâncu Adăugată de avatar Catalin.Francu 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 stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii