Fişierul intrare/ieşire:alohomora.in, alohomora.outSursăAlgoritmiada 2017, Runda 1
AutorEugenie Daniel PosdarascuAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test4 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Alohomora

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 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.

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.

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 seifurile, 0 altfel.

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

Exemplu

alohomora.inalohomora.out
2
3 2 2
2 4
2 5
2 5
2 5
3 1
2 2 2
2 4
2 5
2 4
2 6
1
0
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?