Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | zapezi2.in, zapezi2.out | Sursă | ONIS 2015, Runda 2 |
| Autor | Mihai Calancea | Adăugată de |  Mihai Calancea •klamathix |
| Timp execuţie pe test | 1.4 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Zapezi2
Mai Marii Altui Oraş se confruntă cu o iarnă prelungită. În Alt Oraş există N intersecţii, numerotate de la 1 la N, oricare două fiind conectate direct printr-o stradă bidirecţională. În condiţii meteorologice sumbre, Mai Marii trebuie să fie pregătiţi pentru situaţii de urgenţă. Numim reţea de urgenţă o submulţime de străzi neacoperite de zăpadă, de cardinal minim, care asigură existenţa unui drum direct sau indirect între oricare două intersecţii. Deocamdată există K străzi înzăpezite. Mai Marii Altui Oraş ar dori să ştie câte reţele de urgenţă se pot alcătui momentan modulo 109.
Date de intrare
Fişierul de intrare zapezi2.in va conţine pe prima sa linie numărul de teste T. Pe prima linie a unui test se află numerele N şi K semnificând numărul de intersecţii respectiv numărul de străzi înzăpezite. Urmează K linii fiecare conţinând o pereche A B semnificând faptul că strada care leagă intersecţiile A şi B este înzăpezită.
Date de ieşire
În fişierul de ieşire zapezi2.out se vor afla T linii, fiecare conţinând răspunsul pentru testul corespunzător modulo 109.
Restricţii
- 1 ≤ T ≤ 20
- 1 ≤ N ≤ 10.000
- 1 ≤ K ≤ 18
Exemplu
| zapezi2.in | zapezi2.out |
|---|---|
| 2 3 0 4 3 1 2 1 3 1 4 | 3 0 |
