zapezi2

Zapezi 2

== include(page="template/taskheader" task_id="zapezi2") ==

Poveste şi cerinţă...

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

h2. Date de intrare

Fişierul de intrare $zapezi2.in$ ...

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ă.

h2. Date de ieşire

În fişierul de ieşire $zapezi2.out$ ...

Î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^*.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ T ≤ 20$
* $1 ≤ N ≤ 10.000$
* $1 ≤ K ≤ 16$

h2. Exemplu
table(example). |_. zapezi2.in |_. zapezi2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2
3 0
4 3
1 2
1 3
1 4
| 3
0

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="zapezi2") ==