== include(page="template/taskheader" task_id="tradare") ==
Poveste şi cerinţă...
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.
h2. Date de intrare
Fişierul de intrare $tradare.in$ ...
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$.
h2. Date de ieşire
În fişierul de ieşire $tradare.out$ ...
Î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.
h2. 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$.
h2. Exemplu
table(example). |_. tradare.in |_. tradare.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 2
3 3 3
1 2
2 2
3 2
3 4 1
3 4
| NU
DA
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="tradare") ==
