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 10^9.
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 10 ^ 9.
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 |
