| Fişierul intrare/ieşire: | arugaktus.in, arugaktus.out | Sursă | AGM 2019, runda nationala |
| Autor | Tamio-Vesa Nakajima | Adăugată de |  Tamio Vesa Nakajima •tamionv |
| Timp execuţie pe test | 2.5 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | arugaktus.out |
|---|---|
| 1 5 5 3 1 2 2 3 3 1 1 4 1 5 1 2 3 | 0 0 24 |
