== include(page="template/taskheader" task_id="hacker2") ==
Proaspăt ieşit de pe băncile facultăţii, Bujorel s-a decis că cea mai bună meserie pe care o poate urma este cea de hacker. Astfel, el a dat peste o reţea de $N$ calculatoare, etichetate de la $1$ la $N$, dispuse sub forma unui graf ponderat care este arbore. Fiecare muchie are o pondere, care reprezintă distanţa dintre cele două calculatoare aflate în nodurile muchiei. Distanţa dintre oricare două calculatoare se defineşte ca suma distanţelor de pe lanţul dintre ele.
Înainte de a îşi începe atacul, Bujorel va avea $M$ cerinţe. O cerinţă este de forma unei perechi $(x, p)$, unde $x$ reprezintă indicele unui calculator din arbore, iar $p$ o distanţă. El vrea să determine poziţia de pe o muchie unde poate fi amplasat un nou calculator astfel încât distanţa dintre noul calculator şi calculatorul cu indicele $x$ să fie exact $p$.
h2. Cerinţă
Pentru a deveni ucenicul lui Bujorel, tu trebuie să răspunzi corect la cele $M$ cerinţe.
Poveste şi cerinţă...
h2. Date de intrare
Fişierul de intrare $hacker2.in$ conţine pe prima linie $N$ şi $M$, numărul de calculatoare din reţea, respectiv numărul de întrebări. Următoarele $N–1$ linii conţin triplete de forma $(x, y, d)$ reprezentând o legătură directă între calculatorul $x$ şi calculatorul $y$ de distanţă $d$. Ultimele $M$ linii conţin perechi de forma $(x, p)$ reprezentând cerinţa: “Găsiţi două calculatoare $a$ şi $b$ din arbore între care există o muchie, şi o poziţie $k$ pe muchie, astfel încât suma dintre $k$ şi distanţa de la $x$ la $a$ să fie exact $p$ ”.
Fişierul de intrare $hacker2.in$ ...
h2. Date de ieşire
Fişierul de ieşire $hacker2.out$ va conţine $M$ linii reprezentând răspunsurile la cele $M$ cerinţe. Un răspuns va fi de forma $(a, b, k)$ însemnând că pe muchia dintre calculatoarele $a$ şi $b$ se va amplasa un nou calculator aflat la distanţa $k$ faţă de $a$.
În fişierul de ieşire $hacker2.out$ ...
h2. Restricţii
* $1 ≤ N, M ≤ 100 000$
* $1 ≤ x, y ≤ N$
* $1 ≤ d ≤ 64$
* Pentru un răspuns de forma $(a, b, k)$, $k$ trebuie să fie în intervalul $[0, D(a, b)]$, unde $D(a, b)$ este distanţa de la calculatorul $a$ la calculatorul $b$.
* Toate numerele din fişierele de intrare, respectiv de ieşire vor fi numere naturale.
* Se garantează faptul că pentru fiecare întrebare există un răspuns.
* Orice soluţie corectă este acceptată.
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. hacker2.in |_. hacker2.out |
| 8 4
1 2 1
1 7 1
7 8 1
2 3 1
2 4 1
4 5 1
4 6 1
4 3
2 1
2 3
1 3
| 7 1 0
1 7 0
8 7 0
6 4 0
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="hacker2") ==
