AlgoLiga 2018

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;10⁵] 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 10⁹+7.

Przykład

Wejście:

2
5 0
4 1
2 3

Wyjście:

125
8