== include(page="template/taskheader" task_id="hiking") ==

În ţinuturile îndepărtate, a fost un munte înalt, cu multe sate care il inconjurau. Cele $N$ sate sunt conectate prin $M$ drumuri bidirecţionale cu lungimi integrale pozitive de cel mult $ 10 ^ 9 $. Interesant, sătenii nu au construit mai mult de un drum între perechi de sate şi nu au construit niciodată un drum care să înceapă şi să se termine în acelaşi sat. \\

În ţinuturile îndepărtate, a fost un munte înalt, cu multe sate care il inconjurau. Cele $N$ sate sunt conectate prin $M$ drumuri bidirecţionale cu lungimi intregi pozitive de cel mult $10^9$. Interesant, sătenii nu au construit mai mult de un drum între perechi de sate şi nu au construit niciodată un drum care să înceapă şi să se termine în acelaşi sat. \\

Legendarul excursionist, Artskjid, a început să exploreze aceste sate. Desigur, el a fost uşor să găsească lungimile celor mai scurte căi între orice pereche de sate. Cu toate acestea, acum vrea să urmărească o nouă provocare. Pentru $ Q $ ($ Q \ leq 100.000 $) perechi de sate $ (x, y) $, şi un număr întreg $ p \ în \ {0, 1 \ $ $, el doreşte să ştie dacă există unele \ nu neapărat simplu} calea (adică calea poate vizita noduri sau muchii de mai multe ori) de la $ x $ la $ y $ de lungime $ l $ astfel încât $ l \ equiv p \ pmod 2 $.
h2. Date de intrare