== include(page="template/taskheader" task_id="alohomora") ==
Se dau $N$ chei si $M$ seife. Fiecare cheie respectiv seif are $2$ caracteristici: rang si index. Scopul vostru este sa spuneti daca puteti sa deschideti toate seifele conform urmatoarelor $3$ reguli:
Se dau $N$ chei si $M$ seifuri. Fiecare cheie respectiv seif are $2$ caracteristici: rang si index. Scopul vostru este sa spuneti daca puteti sa deschideti toate seifurile conform urmatoarelor $3$ reguli:
* O cheie de rang $X$ poate sa deschida orice seif de rang $Y$ daca $Y < X$
* O cheie de rang $X$ si index $A$ poate sa deschida un seif de rang $X$ si index $B$ doar daca $A = B$
* Daca aveti $K$ chei de rang $X$, le puteti transforma intr-o cheie de rand $X + 1$ si orice index doriti
* O cheie de rang $X$ poate sa deschida orice seif de rang $Y$ daca $Y < X$.
* O cheie de rang $X$ si index $A$ poate sa deschida un seif de rang $X$ si index $B$ doar daca $A = B$. Daca exista o astfel de pereche, aceasta trebuie obligatoriu facuta.
* Daca aveti $K$ chei de rang $X$, le puteti transforma intr-o cheie de rang $X + 1$ si orice index doriti.
h2. Date de intrare
Fişierul de intrare $alohomora.in$ va contine pe prima linie un numar natural $T$ reprezentand numarul de teste. Pe prima linie a fiecarui test se vor afla cate $3$ numere $N$,$M$ si $K$. Pe urmatoarele $N$ linii se vor afla cate doua numere reprezentand rangul si indexul fiecarei chei. Pe urmatoarele $M$ linii se vor afla cate doua numere reprezentand rangul si indexul fiecarui seif.
Fişierul de intrare $alohomora.in$ va contine pe prima linie un numar natural $T$ reprezentand numarul de teste. Pe prima linie a fiecarui test se vor afla cate $3$ numere $N$, $M$ si $K$. Pe urmatoarele $N$ linii se vor afla cate doua numere reprezentand rangul si indexul fiecarei chei. Pe urmatoarele $M$ linii se vor afla cate doua numere reprezentand rangul si indexul fiecarui seif.
h2. Date de ieşire
Fişierul de ieşire $alohomora.out$ va contine $T$ linii, pe fiecare linie $i$ reprezentand raspunsul pentru testul $i$. Acesta va fi $1$ daca puteti sa deschideti toate seifele, $0$ altfel.
Fişierul de ieşire $alohomora.out$ va contine $T$ linii, pe fiecare linie $i$ reprezentand raspunsul pentru testul $i$. Acesta va fi $1$ daca puteti sa deschideti toate seifurile, $0$ altfel.
h2. Restricţii
* $1 ≤ T ≤ 10$
* $1 ≤ N, M, K ≤ 100.000$
* Rangurile si Index-urile vor fi numere naturale din intervalul $[1, 1.000.000.000]$
* O cheie poate sa fie folosita o singura data
h2. Exemplu
