Fişierul intrare/ieşire:	droom.in, droom.out	Sursă	AGM 2019, runda finala, ziua 1
Autor	Tamio-Vesa Nakajima	Adăugată de	Patrick Sava •xtreme77
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

Droom

Excentricul Primar Droom a implementat un nou sistem de drumuri ciudat in municipiul Suieb. Municipiul poate fi reprezentat drept un graf neorientat cu N (1 <= N <= 20 ) noduri si M (M<=10.000) muchii. Se retine ca pot exista si muchii paralele. Intai numara zilele consecutiv, incepand cu ziua 0. In ziua 0, el face toate drumurile cu sens unic, intr-o directie data. De asemenea, defineste f(i) drept suma modulo 2 a cifrelor lui i. Intr-o zi i, daca f(i) = 0, atunci drumurile sunt cu sens unic, in aceeasi directie ca in ziua 0, pe cand, daca f(i) = 1, atunci drumurile sunt cu sens unic, in directie opusa. De asemenea, acesta mai introduce o noua regula: poti trece doar o data pe zi de la o intersectie la alta – desigur, folosind drumurile regulamentare, adica in directia specifica zilei date. Se garanteaza ca acest lucru este posibil in orice intersectie, in orice zi. Gabitza, un cetatean inocent al municipiului, isi pune intrebarea: dandu-se Q( Q <= 200 ), trei valori a, b, c, ($) si presupunand ca Gabitza este la intersectia a_i in ziua 0, in cate moduri poate Gabi sa ajunga la intersectia b_i in ziua c_i, modulo 10⁹+7?

Date de intrare

Fişierul de intrare droom.in va contine pe prima linie un numar T, numarul de teste.
Fiecare test este format din cateva randuri. Primul rand contine doua numere naturale N, M. Urmatoarele M randuri contin perechi de numere a b, reprezentand ca exista un drum intre intersectiile a b si ca drumul este cu sens unic de la a spre b, in ziua 0. Urmatorul rand contine Q. Urmatoarele Q randuri contin valorile a_i, b_i, c_i, in ordine.

Date de ieşire

În fişierul de ieşire droom.out va contine raspunsurile pentru fiecare test, in ordine. La fiecare test, se va afisa raspunsul pentru fiecare cerinta in ordine, pe randuri separate.

Restricţii

• 1 ≤ N ≤ 20
• M ≤ 10.000
• Q ≤ 200
• 1 ≤ a_i,b_i ≤ N
• 0 ≤ c_i ≤ 10¹⁸
• T ≤ 50

Exemplu

Cum se trimit solutii?