둥둥섬 다리 재정비하기

라이언은 Secret Forest에 오기 전, 둥둥섬의 왕위 계승자였다. 이 이야기는 라이언이 아직 둥둥섬에 살고 있었을 때의 이야기이다.

둥둥섬은 $N$개의 작은 섬들이 $N-1$개의 다리를 통해 이어진 트리 구조를 이룬다. 둥둥섬의 다리는 모두 지나가는 데에 필요한 시간이 2이다.

라이언은 왕위 계승 후의 일에 대한 공부가 되도록 둥둥섬의 다리들을 재정비하는 사업을 지도하게 되었다. 다리를 재정비하면 지나가는 데에 필요한 시간이 1로 줄어든다.

라이언이 다리 재정비 계획을 세우던 중, 둥둥섬의 수도를 이전한다는 소식을 듣게 되었다. 수도는 둥둥섬의 중심이므로, 라이언은 다리를 재정비할 때 다른 모든 섬들에서 수도까지 가는 데에 걸리는 시간의 합을 최소로 하고 싶다.

라이언은 아직 재정비할 다리의 수를 결정하지 못했고, 새로운 수도의 위치도 아직 전달받지 못했다. 수도와 재정비할 다리의 수가 주어질 때마다 적절히 다리들을 재정비했을 때 다른 모든 섬들에서 수도까지 가는 데에 걸리는 시간의 합의 최솟값을 구해 라이언을 도와주자.

첫 줄에 섬의 수 $N$과 쿼리의 수 $Q$가 주어진다. $(1 \leq N,Q \leq 300\,000)$

이후 $N-1$개의 줄에 걸쳐 다리들이 연결하는 두 섬 $u$와 $v$가 공백으로 구분되어 주어진다. $(1 \leq u,v \leq N)$

이후 $Q$개의 줄에 걸쳐 쿼리가 주어진다. $u$와 $a$가 공백으로 구분되어 주어진다. 이는 수도를 $u$로 하고 $a$개의 다리를 재정비한다는 뜻이다. $(1 \leq u \leq N, 0 \leq a \leq N-1)$

각 쿼리의 답을 순서대로 줄바꿈으로 구분하여 출력한다.