Fişierul intrare/ieşire:zapezi2.in, zapezi2.outSursăONIS 2015, Runda 2
AutorMihai CalanceaAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test2.8 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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 diferite 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 ≤ 16

Exemplu

zapezi2.inzapezi2.out
2
3 0
4 3
1 2
1 3
1 4
3
0
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?