== include(page="template/taskheader" task_id="imunitate") ==

Dupa scandalul cu votul noului Cod $Penal$ se doreste o restructurare. S-a gasit o lista de perechi de deputati care daca ar ramane impreuna s-ar influenta reciproc in mod negativ. Se doreste ca noua Camera a Deputatilor sa nu mai fie la fel de $penala$. Asta inseamna ca nici un deputat sa nu fie influentat in mod negativ de mai mult de jumatate din colegii lui. Astfel se alege cate un deputat care nu respecta aceasta conditie si este eliminat. Sa se afle numarul de moduri in care se poate forma o Camera a Deputatilor care sa nu fie $penala$.

Dupa scandalul cu votul noului Cod $Penal$ se doreste o restructurare. S-a gasit o lista de $M$ perechi de deputati care daca ar ramane impreuna s-ar influenta reciproc in mod negativ. Se doreste ca noua Camera a Deputatilor sa nu mai fie la fel de $penala$. Asta inseamna ca nici un deputat sa nu fie influentat in mod negativ de mai mult de jumatate din colegii lui. Astfel se alege cate un deputat care nu respecta aceasta conditie si este eliminat. Sa se afle numarul de moduri in care se poate forma o Camera a Deputatilor care sa nu fie $penala$.

h2. Date de intrare

Fişierul de intrare $imunitate.in$ ...

Fişierul de intrare $imunitate.in$ contine pe prima linie $T$, numarul de teste. Pentru fiecare gaseste o linie cu 2 numere naturale: $N$ reprezentand numarul de deputati, respectiv M, numarul de perechi. Urmatoarele M linii contin cate doua numere naturale x si y, care indica faptul ca deputatii x si y se influenteaza in mod negativ.

h2. Date de ieşire

În fişierul de ieşire $imunitate.out$ ...

În fişierul de ieşire $imunitate.out$ se va scrie pe cate o linie rezultatul cerut pentru fiecare din cele T teste.

h2. Restricţii