Fişierul intrare/ieşire:	hvrays.in, hvrays.out	Sursă	Selectie echipe ACM ICPC, UPB 2007
Autor	Mugurel Ionut Andreica	Adăugată de	Mugurel-Ionut Andreica •mugurelionut
Timp execuţie pe test	0.275 sec	Limită de memorie	67583 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Hvrays

Se dau H raze orizontale si V raze verticale. O raza orizontala este o linie dreapta care are originea intr-un punct si se extinde la infinit spre dreapta (spre coordonate X crescatoare). O raza verticala este o linie dreapta ce are originea intr-un punct si se extinde la infinit in jos (catre coordonate Y descrescatoare). O raza orizontala a carei origine este (X_h,Y_h) atinge o raza verticala a carei origine este (X_v,Y_v) daca X_h ≤ X_v si Y_h ≤ Y_v.

Determinati o submultime S constand dintr-un numar minim de raze verticale astfel incat fiecare raza orizontala sa fie atinsa de cel putin o raza verticala din S. Se garanteaza ca pe testele folosite va exista o astfel de submultime.

Date de intrare

Prima linie a fisierului de intrare hvrays.in contine un numar intreg T, reprezentand numarul de teste ce urmeaza. Prima linie a fiecarui test contine 2 numere intregi: H si V. Urmatoarele H linii contin cate 2 numere intregi: X si Y, reprezentand coordonatele (X,Y) ale originilor razelor orizontale. Urmatoarele V linii contin cate 2 numere intregi: X si Y, reprezentand coordonatele (X,Y) ale originilor razelor verticale.

Date de iesire

Pentru fiecare din cele T teste date, in ordinea din fisierul de intrare, afisati in fisierul de iesire hvrays.out o linie continand numarul minim de raze verticale ale submultimii S.

Restrictii

• 1 ≤ T ≤ 12
• 1 ≤ H ≤ 100 000
• 1 ≤ V ≤ 100 000
• Coordonatele originilor tuturor razelor sunt numere intregi din intervalul [0,50 000 000].

Exemplu

Explicatie

Solutia poate consta din a doua si a treia raza verticala. O alta solutie poate fi formata din prima si a treia raza verticala.

Cum se trimit solutii?