Un pattern de deblocare deseneaza pe un ecran cateva segmente intre puncte, respectand urmatoarele reguli: poate porni din orice punct, foloseste doar segmentele desenate, fiecare segment este parcurs cel mult o data, traseul se incheie in punctul de plecare si degetul nu se ridica de pe ecran pe tot parcursul. Se dau T candidati , fiecare descris printr-o multime de puncte si segmente intre ele. Pentru fiecare candidat trebuie determinat daca segmentele lui pot fi parcurse printr-un astfel de traseu (un circuit eulerian pe graful format de segmentele desenate, ignorand punctele izolate). Determinati pentru cati dintre cei T candidati acest lucru este posibil.
- Date de intrare
- Pe prima linie se citeste T, numarul de candidati. Pentru fiecare candidat se citesc pe o linie doua numere P si E (numarul de puncte, respectiv de segmente), urmate de E linii, fiecare continand doua numere u v (1-indexate) reprezentand un segment intre punctele u si v.
- Date de iesire
- Se afiseaza un singur numar intreg: numarul de candidati pentru care exista un traseu valid.
- Restrictii
- 1 <= T <= 10, 2 <= P <= 15, 1 <= E <= P*(P-1)/2, fiecare segment apare o singura data
Exemple
Exemplul 1
Intrare
3 3 3 1 2 2 3 3 1 3 2 1 2 2 3 6 6 1 2 2 3 3 1 4 5 5 6 6 4
Iesire
1
Exemplul 2
Intrare
4 4 4 1 2 2 3 3 4 4 1 4 6 1 2 1 3 1 4 2 3 2 4 3 4 5 6 1 2 2 3 3 1 1 4 4 5 5 1 2 1 1 2
Iesire
2