Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | alianta.in, alianta.out | Sursă | Algoritmiada 2013, Runda 4 |
| Autor | Cosmin Silvestru Negruseri | Adăugată de |  Eugenie Daniel Posdarascu •eudanip |
| Timp execuţie pe test | 0.4 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | alianta.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.
