Fişierul intrare/ieşire:imunitate.in, imunitate.outSursăONIS 2014, Runda 1
AutorCazacu AlexandruAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.9 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Imunitate

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.

Date de intrare

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.

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.

Restricţii

  • 1 ≤ T ≤ 20
  • 1 ≤ N ≤ 18
  • 1 ≤ M ≤ N^2
  • E posibil ca aceeasi pereche de deputati sa apara de mai multe ori
  • Doua modalitati sunt diferite daca difera deputatii ramasi.

Exemplu

imunitate.inimunitate.out
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

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content