MooTube (Gold)

농부 존은 남는 시간에 동영상 공유 서비스 MooTube를 만들었다. MooTube에서 존의 소들은 재미있는 동영상을 서로 나눠 본다. 소들이 이미 올려 둔 동영상은 $N$개이고, 1번부터 $N$번까지 번호가 붙어 있다. 하지만 존은 소가 마음에 들 만한 새 동영상을 어떻게 찾게 해 줄지 아직 좋은 방법을 떠올리지 못했다.

존은 동영상마다 연관 동영상 목록을 만들기로 했다. 그러면 소는 지금 보고 있는 동영상과 가까운 동영상을 추천받는다.

두 동영상이 얼마나 가까운지는 존이 만든 USADO라는 값으로 잰다. 존은 동영상 쌍 $N-1$개를 골라 그 쌍의 USADO를 직접 계산했다. 이 $N-1$개의 쌍은 어떤 동영상에서 다른 어떤 동영상으로 가는 경로가 정확히 하나만 존재하도록 골랐다. 동영상을 정점으로 보고 직접 잰 쌍을 간선으로 보면 전체가 하나의 트리다. 직접 재지 않은 두 동영상의 USADO는 둘을 잇는 경로에 놓인 간선의 USADO 중 최솟값이다.

존은 동영상 하나를 정하고 값 $K$를 정한 다음, 그 동영상과의 USADO가 $K$ 이상인 동영상을 모두 추천한다. 추천이 너무 많으면 소가 일을 못 하니 $K$를 잘 골라야 한다. $K$와 동영상 번호가 주어질 때 추천되는 동영상이 몇 개인지 답하라.

첫 줄에 동영상의 수 $N$과 질문의 수 $Q$가 주어진다. ($1 \le N \le 100\,000$, $1 \le Q \le 100\,000$)

다음 $N-1$개의 줄에는 존이 직접 잰 값이 한 줄에 하나씩 주어진다. 각 줄은 세 정수 $p_i$, $q_i$, $r_i$로 이루어지며 ($1 \le p_i, q_i \le N$, $1 \le r_i \le 1\,000\,000\,000$), 동영상 $p_i$와 $q_i$가 USADO $r_i$로 이어져 있다는 뜻이다.

다음 $Q$개의 줄에는 질문이 한 줄에 하나씩 주어진다. 각 줄은 두 정수 $k_i$와 $v_i$로 이루어지며 ($1 \le k_i \le 1\,000\,000\,000$, $1 \le v_i \le N$), $K = k_i$일 때 동영상 $v_i$를 보고 있는 소에게 추천되는 동영상이 몇 개인지 묻는다.

$Q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 질문의 답을 출력한다.

예제에서 1번과 2번의 USADO는 3, 2번과 3번의 USADO는 2, 2번과 4번의 USADO는 4다. 여기서 1번과 3번의 USADO는 $\min(3, 2) = 2$, 1번과 4번의 USADO는 $\min(3, 4) = 3$, 3번과 4번의 USADO는 $\min(2, 4) = 2$가 된다.

$K = 1$이고 2번 동영상을 볼 때 추천되는 동영상은 1번, 3번, 4번이다. $K = 4$이고 1번 동영상을 볼 때는 추천되는 동영상이 없다. $K = 3$이고 1번 동영상을 볼 때는 2번과 4번이 추천된다.