Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_21_11 - Sieć dróg

Niedawno w Bitocji miała miejsce erupcja wulkanu w wyniku której niektóre drogi zostały doszczętnie zniszczone. Przed erupcją sieć dróg miała własności takie, że z każdego miasta dało się dojechać do każdego innego, w dokładnie jeden sposób. Kataklizm spowodował, że z niektórych miast nie da się teraz dojechać do innych. Król Bitocji Bitazar natychmiast po tym wydarzeniu nakazał wybudowanie nowych dróg. Gdy wybierał, które drogi mają być zbudowane zastanowiła go jedna rzecz. Na ile sposobów może wybrać drogi tak, aby z każdego miasta dało się dojechać do każdego innego, oraz liczba wybranych dróg jest minimalna? Nie potrafiąc znaleźć odpowiedzi na to pytanie poprosił Ciebie o pomoc.

Wejście

W pierwszej linii liczba zestawów danych t ∈ [1;10].

W pierwszej linii każdego zestawu danych znajdują się dwie liczby n ∈ [1;105] i m ∈ [0;n) oznaczające kolejno liczbę miast i liczbę dróg które się ostały.

W kolejnych m liniach każdego zestawu danych znajdują się po dwie liczby v i u oznaczające, że ostała się droga łącząca miasto v z miastem u.

Wyjście

Dla każdego zestawu danych wypisz wynik modulo 109+7.

Przykład

Wejście:

2
5 0
4 1
2 3

Wyjście:

125
8

Dodane przez:Bartek
Data dodania:2015-03-06
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY
Pochodzenie:ALGOLIGA
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.