Fişierul intrare/ieşire:alianta.in, alianta.outSursăAlgoritmiada 2013, Runda 4
AutorCosmin Silvestru NegruseriAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test0.8 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Alianta

Clanurile Uchiha si Senju au decis sa faca o alianta impreuna cu alte clanuri. Se stie ca in total avem N clanuri numerotate de la 1 la N si M relatii de tipul (x,y) reprezentand faptul ca clanul x nu poate sa faca alianta cu clanul y. Clanul Nara trebuie sa aleaga cat mai multe clanuri care sa faca parte din alianta astfel incat sa se respecte cele M relatii. Ajutati clanul Nara sa determine numarul maxim de clanuri ce pot face parte din alianta.

Date de intrare

Fişierul de intrare alianta.in va contine pe prima linie numarul T reprezentand numarul de teste. Pe prima linie din fiecare test se afla 2 numere naturale N si M cu semnificatia din enunt. Urmatoarele M linii vor contine cele M relatii de tipul (x,y).

Date de ieşire

Fişierul de ieşire alianta.out va contine T linii, pe linia i raspunsul la testul i.

Restricţii

  • 1 ≤ T ≤ 10
  • 1 ≤ N ≤ 36
  • 0 ≤ M ≤ 630

Exemplu

alianta.inalianta.out
1
8 12
1 2
2 3
3 4
4 1
5 6
6 7
7 8
8 1
1 5
2 6
3 7
4 8
4

Explicaţie

Cele 4 clanuri care pot forma o alianta sunt 2, 4, 5 si 7.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content