問題文

N 頂点の木があります。この木の辺の長さはすべて 1 です。この木の上で Q 回鬼ごっこをします。あなたは逃げる側であり、鬼ごっこの開始時に鬼はあなたと異なる頂点にいます。鬼はあなたのいる場所を常に知っていて、毎秒 1 の速さであなたを追いかけます。あなたは鬼の位置はわかりませんが、鬼までの距離は鬼の匂いの濃度から常にわかります。その情報をもとに、毎秒以下の 2 つの動作のうち 1 つを行います。

• 1 秒かけて隣接する頂点に進む
• 1 秒間今いる頂点で静止する

辺上か頂点上で鬼と会ったら、その回の鬼ごっこは終了です。

i 回目の鬼ごっこの開始時では、あなたは頂点 x_i にいて、鬼までの距離が d_i であることがわかっています。鬼と出会うまでの時間の最小値を最大化するように行動したときの、鬼に会うまでの時間の最小値 s_i を求めてください。

(つまり、答えはあなたは得られた情報から賭けをすることなく鬼と出会わないように動くときの鬼と出会うまでの時間の最小値です。また、辺上での移動は等速運動とし、鬼はあなたとの距離を縮める方向に動きます。)

制約

• 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
• 頂点 x_i から距離が d_i である頂点は必ず存在する。
• i \neq j のとき (x_i, d_i) \neq (x_j, d_j)
• 与えられるグラフは必ず木である。
• 入力は全て整数である。

入力例1

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

出力例1

4
1

1 回目の鬼ごっこの開始時には、あなたは頂点 1 にいて、鬼までの距離は 4、つまり鬼は頂点 5 にいます。このときは、頂点 1 にずっととどまる行動が最適となり、s_1 = 4 となります。

2 回目の鬼ごっこの開始時には、あなたは頂点 3 にいて、鬼までの距離は 1、つまり鬼は頂点 2 か頂点 4 のどちらかにいます。この後あなたが頂点 2 の方向に動いたとすると、鬼がはじめ頂点 2 にいたときは、0.5 秒後に辺上で出会い、頂点 4 にいたときは、3 秒後に頂点 1 で出会います。よって、この行動をしたときの鬼と出会うまでの最小値は 0.5 となります。 頂点 4 の方向に動いたときも同様に鬼と出会うまでの最小値は 0.5 となります。 もし、あなたが動かず頂点 3 にとどまっていたとすると、鬼が頂点 2 にいたとき 1 秒後に、頂点 4 にいたときも 1 秒後に出会います。よって、この行動をしたときの鬼と出会うまでの最小値は 1 となります。

したがって、あなたの最適な行動は頂点 3 にとどまることで、その時の鬼に会うまでの時間の最小値 s_2 は 1 となります。

入力例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

出力例2

2
5