无垢之土
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

原初的质料
无瑕的生命
白垩色的王子给了你一棵由 n 个点和 n-1 条双向边连成的无根树，所有边的长度均为 1。
在若干个时刻，会有若干个生物在某个结点出生，共 m 个生物。具体地，第 i 个生物在 a_i 结点出生，出生时刻为 t_i。第 i 个生物于 t_i 时刻出生后，其在之后的任意时刻可能会保持静止，也可能以 1 单位每时刻的速度沿树边进行移动。
现在询问，在哪一时刻，第一次可能有生物相遇。
容易发现该时刻一定是一个整数或分母为 2 的分数，因此便捷起见，请你输出该时刻的两倍。

输入描述:

第一行输入两个整数 n,m(1\le n \le 10^5,2\le m \le 10^5)，分别表示点数和生物数。
接下来 n-1 行，每行包含两个整数 u,v(1\le u,v \le n)，表示在 u,v 之间存在一条双向边，保证这 n-1 条边构成一棵树。
接下来 m 行，每行包含两个整数 a_i,t_i(1\le a_i\le n,0\le t_i \le 10^6)，分别表示生物 i 的出生结点与出生时刻。

输出描述:

输出一个数，表示第一次可能有生物相遇的时刻的两倍。
示例1

输入

复制 
5 3
1 2
1 3
2 4
2 5
1 4
3 2
4 0

输出

复制 
5

说明

出生在结点 3 的生物和出生在结点 4 的生物沿路径 4-2-1-3 行走，会在 2.5 时刻相遇。
示例2

输入

复制 
2 2
1 2
1 0
1 0

输出

复制 
0