În lipsa prinţesei cu ochii verzi, tărâmul ei fermecat a fost invadat de termite! Se ştie despre tărâmul fermecat că este organizat sub forma unui graf conex neorientat, în care fiecare muchie are atribuită o lungime. Prinţesa  nu poate să combată această invazie, însă ea a aflat informaţii preţioase despre aceste termite. Se ştie că invazia a pornit simultan din exact $K$ noduri, la un moment de timp pe care îl vom nota cu 0. Aceste termite, o dată aflate într-un nod, îl manâncă instant, se înmultesc şi pornesc pe muchiile incidente nodului către nodurile vecine. Astfel, dacă o termită ajunge într-un nod la un moment de timp $T$, tot în acelaşi moment termitele îl vor mânca, se vor înmulţi şi vor porni către celelalte noduri. Prinţesa mai ştie de altfel că timpul lor de deplasare este constant şi că acestea parcurg o muchie de lungime $L$ exact în $L$ secunde. Un nod o dată mâncat, acesta va dispărea din graf, însă nu neapărat şi muchiile incidente lui (muchia va ramâne în graf atâta timp cât este incidentă cel puţin unui nod). Altfel zis, o muchie va dispărea doar atunci când ambele noduri de la capete ei vor fi mâncate.
Prinţesa nu îşi poate salva întregul regat, însă ar dori să ştie dacă ar putea salva unele comori care se află în anumite noduri ale grafului. Astfel, ea va va pune $Q$ întrebări de forma $A B T$ cu următoarea semnificaţie: ştiind că prinţesa se află la momentul $T$ în nodul $A$, iar comoara se află în  nodul $B$, câte secunde se vor scurge până când nu va mai exista niciun drum între ea şi comoară (aceasta se poate întampla şi în cazurile în care nodul $A$ sau nodul $B$ este mâncat). Dacă încă din momentul $T$ nu există niciun drum între cele două noduri, atunci se va afişa $0$.

h2.Cerinta

h2. Cerinta

Ajutaţi-o pe prinţesă, raspunzând corect la toate cele $Q$ întrebari.

table(example). |_. termite.in |_. termite.out |
| 5 6 1 3
5

1 2 3

1 2 3

1 5 3
2 3 2
2 4 1

3 5 2
1 3 1
1 4 3

2 5 1

2 5 1

| 1
0
0