Fişierul intrare/ieşire:	tradare.in, tradare.out	Sursă	ONIS 2015, Runda Finala
Autor	Mihai Calancea	Adăugată de	ONIS2015 •ONIS2015
Timp execuţie pe test	0.75 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/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.

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 ≤ 100
• 1 ≤ N, M ≤ 100.000
• 0 ≤ K ≤ min(100.000, N x M - 1)
• Cele K parcele vor fi distincte. În plus, se garantează că va exista întotdeauna cel puţin o parcelă liberă.

Exemplu

Cum se trimit solutii?