快递员

题目描述

Bob 的城市里有 $n$ 个邮递站,由于经济考虑,这些邮递站被 $n - 1$ 条带权无向边相连。即:这 $n$ 个邮递站构成了一棵树。 Bob 正在应聘一个快递员的工作,他需要送 $m$ 个商品,第 $i$ 个商品需要从 $u$ 送到 $v$。由于 Bob 不能带着商品走太长的路,所以对于一次送货,他需要先从快递中心到 $u$,再从 $u$ 回到快递中心,再从快递中心到 $v$,最后从 $v$ 返回快递中心。换句话说,如果设快递中心是 $c$ 号点,那么他的路径是 $c \rightarrow u \rightarrow c \rightarrow v \rightarrow c$。 现在 Bob 希望确定一个点作为快递中心,使得他送货所需的最长距离最小。显然,这个最长距离是个偶数,你只需要输出最长距离除以 $2$ 的结果即可。

输入输出格式

输入格式


第一行输入两个数 $n, m$,意义如上。 接下来$n-1$行,每行三个数 $u_i, v_i, w_i$,表示一条连接 $u_i, v_i$,长度为 $w_i$ 的边。 接下来 $m$ 行,每行两个整数 $u_i, v_i$,表示商品的起止位置。

输出格式


一行一个整数,表示答案。

输入输出样例

输入样例 #1

3 1
1 2 1
2 3 1
1 3

输出样例 #1

2

说明

对于 $25\%$ 的数据,满足 $1 \leq n, m \leq 1000$。 对于 $100\%$ 的数据,满足 $1 \leq n, m \leq 10^5, 1 \leq w_i \leq 1000$。