Problem Description

In Bob’s city, there are $n$ post stations. For economic reasons, these stations are connected by $n - 1$ weighted undirected edges. That is, the $n$ post stations form a tree.

Bob is applying for a courier job. He needs to deliver $m$ packages. For the $i$-th package, it needs to be delivered from $u$ to $v$. Since Bob cannot carry a package for too long, for one delivery, he must first go from the courier center to $u$, then return from $u$ to the courier center, then go from the courier center to $v$, and finally return from $v$ to the courier center. In other words, if the courier center is node $c$, then his route is $c \rightarrow u \rightarrow c \rightarrow v \rightarrow c$.

Now Bob wants to choose a node as the courier center so that the maximum distance he needs for any delivery is minimized. Clearly, this maximum distance is an even number. You only need to output the result of dividing the maximum distance by $2$.

Input Format

The first line contains two integers $n, m$, with the meanings as described above.

The next $n - 1$ lines each contain three integers $u_i, v_i, w_i$, representing an edge connecting $u_i$ and $v_i$ with length $w_i$.

The next $m$ lines each contain two integers $u_i, v_i$, representing the start and end locations of a package.

Output Format

Output one integer on a single line, representing the answer.

3 1
1 2 1
2 3 1
1 3

2

Hint

For $25\%$ of the testdata, $1 \leq n, m \leq 1000$.

For $100\%$ of the testdata, $1 \leq n, m \leq 10^5$, $1 \leq w_i \leq 1000$.

Translated by ChatGPT 5