imunitate

Imunitate

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

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

Camera Deputatilor este formata din $N$ deputati, numerotati de la 1 la $N$. 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 $penala$. Asta inseamna sa nu existe un deputat care sa fie influentat in mod negativ de mai mult de jumatate din colegii lui ramasi. 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$ 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.

Fişierul de intrare $imunitate.in$ contine pe prima linie $T$, numarul de teste. Pentru fiecare se gaseste o linie cu $2$ numere naturale: $N$ si $M$ cu semnificatiile din enunt. Urmeaza $M$ linii care contin cate doua numere naturale $ZG$ si $PO$ si indica faptul ca deputatii $ZG$ si $PO$ se influenteaza in mod negativ.

h2. Date de ieşire

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

Î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

* $1 ≤ N ≤ 20$

* $1 ≤ T ≤ 20$
* $1 ≤ N ≤ 18$

* $1 ≤ M ≤ N^2$

* E posibil sa aceeasi pereche de deputati sa apara de mai multe ori

* E posibil ca aceeasi pereche de deputati sa apara de mai multe ori
* Doua modalitati sunt diferite daca difera deputatii ramasi.

h2. Exemplu
table(example). |_. imunitate.in |_. imunitate.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2
4 6
1 2
1 3
1 4
2 3
2 4
3 4
4 4
1 2
3 2
1 3
4 2
| 4
3

|
h3. Explicaţie

...

$Pentru primul exemplu, cele patru posibilităţi sunt: 1; 2; 3; 4.$
$Pentru al doilea exemplu, cele trei posibilităţi sunt: 1, 3, 4; 1, 4; 4, 3.$

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

9420