사자와 얼룩말

트리가 $N$개의 정점으로 주어진다. 이 트리에서 술래잡기 게임을 한다. 게임은 여러 라운드로 이루어진다. 각 라운드에는 두 플레이어가 있다. 잡는 쪽인 사자와 도망치는 쪽인 얼룩말이다. 라운드 시작 시 얼룩말과 사자는 서로 다른 두 정점에 있다. 사자는 얼룩말의 위치를 항상 알고, 1초에 간선 하나의 속도로 얼룩말을 쫓는다. 얼룩말은 사자의 위치를 모르지만 사자와의 거리는 항상 안다. 얼룩말은 매초 다음 둘 중 하나를 고른다. 인접한 정점으로 1초 동안 이동하거나, 현재 정점에 1초 동안 머문다. 얼룩말이 간선 위나 정점에서 사자와 만나면 라운드가 끝난다. 두 플레이어가 같은 간선을 따라 서로를 향해 움직이면 이동을 시작하고 0.5초 뒤에 만난다. 얼룩말은 사자가 가능한 모든 초기 정점에 대해, 사자와 만나는 최소 시간의 최솟값이 최대가 되도록 행동한다. Q개의 라운드가 주어진다. i번째 라운드에서 얼룩말은 정점 $v_i$에서 출발하고, 사자와의 거리는 $d_i$이다. 각 라운드에 대해 양측이 전략대로 행동할 때 라운드가 끝나는 최소 시간을 구하라.

첫 줄에 트리의 정점 수 $N$과 라운드 수 $Q$가 주어진다($2 \le N \le 10^5$, $1 \le Q \le 10^5$). 이후 $N-1$개의 줄에 간선으로 연결된 두 정점 $a_i$, $b_i$가 주어진다. 주어진 그래프는 트리이다. 이후 $Q$개의 줄에 얼룩말의 시작 정점 $v_j$와 얼룩말에서 사자까지의 거리 $d_j$가 주어진다($1 \le v_j \le N$, $1 \le d_j \le N-1$). $v_j$에서 거리가 $d_j$인 정점 $w_j$가 적어도 하나 존재한다고 가정해도 된다.

각 질의에 대해 양측이 전략대로 행동할 때 라운드가 끝나는 최소 시간을 정수 하나로 출력한다.

예제 1의 첫 번째 라운드에서 얼룩말은 정점 1에 있고 사자와의 거리는 $4$이므로, 사자는 정점 5에 있다. 최적 전략은 정점 1에 최대한 오래 머무르는 것이며, 답은 $4$이다. 두 번째 라운드에서 얼룩말은 정점 3에 있고 사자와의 거리는 $1$이므로, 사자는 정점 2 또는 정점 4에 있다. 얼룩말이 정점 2 방향으로 움직이면, 사자가 정점 2에서 출발한 경우 0.5초 뒤 간선 위에서 만나고, 정점 4에서 출발한 경우 정점 1에서 3초 뒤에 만난다. 따라서 이 전략의 최소 시간은 $0.5$이다. 정점 4 방향으로 움직여도 최소 시간은 $0.5$이다. 얼룩말이 정점 3에 머물면, 사자가 정점 2에서 출발하든 정점 4에서 출발하든 1초 뒤에 만난다. 따라서 답은 $1$이다.