== include(page="template/taskheader" task_id="termite") ==
Poveste şi cerinţă...
Î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
Ajutaţi-o pe prinţesă, raspunzând corect la toate cele $Q$ întrebari.
h2. Date de intrare
Fişierul de intrare $termite.in$ ...
Fişierul de intrare $termite.in$ conţine pe prima linie $4$ numere naturale: $n$ – numărul de noduri ale grafului, $m$ - numărul de muchii ale grafului, $k$ – numărul de noduri din care au pornit termitele şi $Q$ – numărul de întrebări. A doua linie a fişierului va conţine $k$ valori, semnificând indicele nodurilor unde au apărut în momentul $0$ termitele. Următoarele $m$ linii vor conţine cate $3$ valori : $a, b şi L$, însemnând că între nodurile $a şi b$ există o muchie de lungime $L$. Următoarele $Q$ linii din fişierul de intrare vor reprezenta query-urile, în forma $A B T$, însemnand câte secunde mai are prinţesa începând de la momentul de timp $T$ până când nu va mai exista drum între nodurile $A şi B$.
h2. Date de ieşire
În fişierul de ieşire $termite.out$ ...
Fişierul de iesire $termite.out$ va conţine $Q$ linii cu câte un singur număr natural reprezentând răspunsurile la cele $Q$ întrebari.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ n, k ≤ 300 000$
* $1 ≤ m, Q ≤ 400 000$
h2. Exemplu
table(example). |_. termite.in |_. termite.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 6 1 3
5
1 2 3
1 5 3
2 3 2
2 4 1
3 4 1
3 5 2
1 3 1
1 4 3
2 5 1
| 1
0
0
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="termite") ==
