Fişierul intrare/ieşire:tradare.in, tradare.outSursăONIS 2015, Runda Finala
AutorMihai CalanceaAdăugată deONIS2015ONIS2015 ONIS2015
Timp execuţie pe test1.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Por Costel și Trădarea

Por Costel şi-a vândut sufletul şi autorii, acceptând să devină personaj într-un enunţ al finalei ONIS. Pentru acest lucru el a primit drept Mită un teren dreptunghic cu N linii şi M coloane, fiecare din cele N x M parcele fiind disponibile pentru cultivarea porumbului. Auzind despre noua oportunitate, prietenii lui Por Costel au început să ocupe unele parcele, pregătindu-se deja pentru recoltă. Fiecare dintre cei K prieteni ai lui Por Costel ocupă exact o parcelă de teren. Por Costel este îngrijorat fiindcă prietenii săi, fiind nişte porci, nu au luat deloc în calcul că pot încurca recoltarea porumbului. Mai exact, el doreşte să afle dacă după ocuparea celor K parcele de către porcii săi de prieteni parcelele libere sunt încă conectate. Spunem că parcelele sunt conectate dacă pentru oricare două parcele libere, A şi B, putem ajunge din A în B, deplasându-ne de fiecare dată într-o parcelă liberă, adiacentă cu cea curentă, fără a ieşi înafara terenului.

Date de intrare

Fişierul de intrare tradare.in va conţine pe prima sa linie numărul de teste T. Urmează T teste, structura unui test fiind următoarea: pe prima linie se află numerele N M K, reprezentând dimensiunile terenului şi numărul de prieteni ai lui Por Costel. Urmează K linii, fiecare conţinând o pereche de numere X Y, reprezentând coordonatele parcelei ocupate de prietenul respectiv ( X fiind linia şi Y coloana). Liniile terenului sunt numerotate de la 1 la N, iar coloanele de la 1 la M.

Date de ieşire

În fişierul de ieşire tradare.out va avea T linii, fiecare conţinând răspunsul pentru testul corespunzător: mesajul "DA" în cazul în care parcelele libere sunt încă conectate, respectiv "NU" în caz contrar.

Restricţii

  • 1 ≤ T ≤ 10.000
  • 1 ≤ N, M ≤ 100.000
  • 0 ≤ K ≤ min(100.000, N x M)
  • O parcelă poate să apară de mai multe ori.
  • Dacă nu există nicio parcelă liberă, răspunsul este DA.
  • Suma valorilor lui K în cadrul aceluiaşi fişier de intrare nu va depăşi 1.000.000.

Exemplu

tradare.intradare.out
2
3 3 3
1 2
2 2
3 2
3 4 1
3 4
NU
DA
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?