Fişierul intrare/ieşire:droom.in, droom.outSursăAGM 2019, runda finala, ziua 1
AutorTamio-Vesa NakajimaAdăugată dextreme77Patrick Sava xtreme77
Timp execuţie pe test5 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/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 noduri si M muchii. Se retine ca pot exista si muchii paralele. Intai numeroteaza zilele consecutiv, incepand cu ziua 0. In ziua 0, impune un sens unic tuturor drumurilor, acest sens fiind dat. De asemenea, defineste f(i) ca fiind suma, modulo 2, a cifrelor lui i, cand i este scris in baza 2. In ziua 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: trebuie sa treci exact o data pe zi de la o intersectie la alta – desigur, folosind drumurile 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 tupluri (ai, bi, ci), si presupunand ca Gabitza este la intersectia ai in ziua 0, in cate moduri poate Gabi sa ajunga la intersectia bi in ziua ci, modulo 109+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 mai multe randuri. Primul rand contine doua numere naturale N, M. Urmatoarele M randuri contin perechi de numere x, y, reprezentand ca exista un drum intre intersectiile x si y, drumul avand sens unic de la x spre y in ziua 0. Urmatorul rand contine Q. Urmatoarele Q randuri contin valorile (ai, bi, ci), in ordine.

Date de ieşire

În fişierul de ieşire droom.out va contine raspunsurile pentru fiecare test, in ordine.
Pentru fiecare test, se va afisa, pe cate un rand, raspunsul pentru fiecare tuplu (ai, bi, ci).

Restricţii

  • 1 ≤ N ≤ 20
  • M ≤ 10.000
  • Q ≤ 200
  • 1 ≤ ai,bi ≤ N
  • 0 ≤ ci ≤ 1018
  • T ≤ 50

Exemplu

droom.indroom.out
2
3 7
3 2
3 2
2 1
1 3
3 2
1 3
2 1
3
1 3 7
1 3 6
1 3 6
3 8
1 2
1 2
1 3
2 3
3 2
2 1
3 1
3 1
3
3 2 8
3 2 4
2 1 2
1
0
0
85
5
1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?