Problem description

Podczas swojego przyjęcia urodzinowego, Jaś grał z przyjaciółmi w Osadników z Catanu. Oczywiście, ze~względu na dużą liczbę gości, rozmiar planszy był zauważalnie większy niż standardowy. Po zakończeniu przyjęcia Jaś zabrał się za sprzątanie. Jednak, jak powszechnie wiadomo, kombinatoryka jest znacznie ciekawsza. Dlatego zamyślił się on stojąc nad planszą…

Na planszy znajduje się N osad, a każda z nich przynosi korzyści jednego z trzech rodzajów: drewno, glinę lub owce. Osady połączone są M drogami, a każda z nich łączy bezpośrednio dwie różne osady i nie krzyżuje się z żadną inną drogą. Osady spełniają poniższe warunki:

• Pomiędzy dowolną parą osad można przejechać istniejącymi drogami.
• Osad jest co najmniej tyle, co dróg.

Jaś chciałby podzielić osady na pewną liczbę kolonii, które byłyby niezależne, tzn. spełniałyby następujące trzy warunki:

1. Każda osada należy do dokładnie jednej kolonii.
2. W każdej kolonii, korzyści każdego rodzaju (drewno, glina, owce) są przynoszone przez co najmniej jedną wioskę.
3. Pomiędzy każdą parą osad należącą do tej samej kolonii można przejechać istniejącymi drogami, nie przejeżdżając przez ani jedną osadę należącą do innej kolonii.

Na ile sposobów Jaś może dokonać takiego podziału? Odpowiedź oblicz modulo 10⁹ + 7.

Powyższy obrazek przedstawia sieć dróg łączących osady w pierwszym przypadku testowym. Kolory wierzchołków reprezentują jakie korzyści przynoszą poszczególne rodzaje osad. Osady można między innymi podzielić na kolonie {1, 2, 3, 4} oraz {5, 6, 7, 8, 9}. Wszystkie osady mogą też stanowić jedną wspólną kolonię. Osady {1, 2, 3} nie stanowią poprawnej kolonii, bo nie spełniają drugiego kryterium. Osady {1, 3, 4} je spełniają, ale za to nie spełniają trzeciego warunku.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna T, oznaczająca liczbę przypadków testowych. Następne wiersze opisują przypadki testowe w następującym formacie.

Pierwszy wiersz przypadku testowego zawiera dwie liczby naturalne N i M, oznaczające liczby osad oraz dróg pomiędzy nimi. Drugi wiersz przypadku testowego składa się z N liczb, pooddzielanych pojedynczymi odstępami, gdzie i-ta liczba jest równa 1, 2 lub 3, co oznacza, że i-ta osada dostarcza odpowiednio drewno, glinę lub owce. Kolejne M wierszy przypadku testowego zawiera po dwie liczby naturalne a oraz b, oznaczające dwukierunkową drogę łączącą osady a oraz b.

Wyjście

Na wyjściu należy wypisać T wierszy. W i-tym z nich powinna znaleźć się jedna liczba naturalna – reszta z dzielenia przez 10⁹ + 7 liczby poprawnych podziałów osad na kolonie w i-tym przypadku testowym.

Ograniczenia

1 ≤ T ≤ 50 000, 1 ≤ N ≤ 50 000, 0 ≤ M ≤ 50 000, 1 ≤ a, b ≤ N.

Ani suma liczb N, ani suma liczb M we wszystkich przypadkach testowych nie przekracza 50 000.

Przykłady

3
9 9
1 1 3 2 2 1 3 1 2
1 2
2 3
3 4
3 5
4 6
5 6
6 7
7 8
7 9
3 3
1 2 3
1 2
2 3
1 3
9 8
1 2 3 1 2 3 1 2 3
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9

5
1
6