Fişierul intrare/ieşire:arugaktus.in, arugaktus.outSursăAGM 2019, runda nationala
AutorTamio-Vesa NakajimaAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test2.5 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Arugaktus

Arugak este foarte interesata de grafuri, deci a definit un nou tip de graf: arugaktusul. Un arugaktus este un graf nedirectionat conex unde oricare ciclu simplu are lungime impara.
Arugak a desenat un arugaktus cu N noduri si M muchii. De asemenea vrea sa cumpere K creioane colorate diferite, dar nu este sigura cat ar trebui sa fie K. Pentru a decide, ea are Q valori posibile pentru K, si vrea sa stie, pentru fiecare valoare, in cate moduri poate colora nodurile arugaktusului cu K culori astfel incat oricare doua noduri legate printr-o muchie sunt colorate diferit, modulo 1.000.000.7. O puteti ajuta ?

Date de intrare

Fişierul de intrare arugaktus.in va contine, pe primul rand, T, numarul de teste ce se gasesc in fisier.
Prima linie a oricarui test va contine numerele N, M, Q, cu semnificatia de mai sus.
Urmatoarele M linii contin o pereche i, j de noduri, care reprezinta ca exista o muchie intre nodul i si nodul j.
Urmatoarele Q linii vor contine cate o valoare diferita a lui K de care e Arugak interesata.

Date de ieşire

În fişierul de ieşire arugaktus.out se vor gasi raspunsurile pentru cele T teste, in ordine.
Pentru fiecare test, afisati, pe cate un rand, raspunsul pentru fiecare valoare a lui K de care este Arugak intersata, in ordine.

Restricţii

  • 1 ≤ T ≤ 20
  • 1 ≤ N ≤ 100.000
  • 1 ≤ Q ≤ 10
  • 1 ≤ K ≤ 1.000.000.000

Exemplu

arugaktus.inarugaktus.out
1
5 5 3
1 2
2 3
3 1
1 4
1 5
1
2
3
0
0
24
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?