Problem Description

There is a tree with $ N $ vertices. The length of each edge in this tree is $ 1 $. You will play hide-and-seek $ Q $ times on this tree. You are the one hiding, and the seeker starts at a different vertex than you. The seeker always knows your location and chases you at a speed of $ 1 $ per second. You do not know the seeker's position, but you always know the distance to the seeker based on the intensity of the seeker's scent. Based on this information, you can perform one of the following two actions each second:

• Move to an adjacent vertex, taking $ 1 $ second
• Stay at the current vertex for $ 1 $ second

If you meet the seeker on an edge or at a vertex, the game ends for that round.

At the start of the $ i $th game, you are at vertex $ x_i $ and know the distance $ d_i $ to the seeker. Determine the minimum time $ s_i $ until you meet the seeker when you act to maximize this minimum time.

(In other words, the answer is the minimum time until you meet the seeker when you move without taking any risks based on the information you have. Also, movement on edges is at constant speed, and the seeker moves towards you to reduce the distance.)

Input Format

The input is given from the standard input in the following format:

$ N $ $ Q $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $\vdots$ $ a_{N-1} $ $ b_{N-1} $ $ x_1 $ $ d_1 $ $ x_2 $ $ d_2 $ $\vdots$ $ x_Q $ $ d_Q $

The first line contains the number of vertices $ N $ and the number of games $ Q $. From the second line to the $ N $th line, the tree's information is given. The $ i+1 $th line indicates that vertices $ a_i $ and $ b_i $ are connected by an edge. From the $ N+1 $th line to the $ N+Q $th line, the information for each game is given. The $ N+i $th line contains the vertex $ x_i $ where you are at the start of the $ i $th game and the distance $ d_i $ to the seeker.

Output Format

$ s_1 $ $ s_2 $ $\vdots$ $ s_Q $

For each game, output the minimum time $ s_i $ until you meet the seeker when you act to maximize this minimum time. It can be shown that $ s_i $ is always an integer.

Sample Input and Output

Sample Input #1

5 2
1 2
2 3
3 4
4 5
1 4
3 1

Sample Output #1

4
1

Sample Input #2

11 2
1 2
2 3
1 4
4 5
1 6
6 7
7 8
1 9
9 10
10 11
3 2
10 4

Sample Output #2

2
5

Notes/Hints

Constraints

• $2 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq a_i, b_i \leq N$
• $1 \leq x_i, d_i \leq N$
• There is always a vertex at distance $ d_i $ from vertex $ x_i $.
• $(x_i, d_i) \neq (x_j, d_j)$ when $i \neq j$
• The given graph is always a tree.
• All inputs are integers.

见题面 Input 部分

见题面 Output 部分