MooTube (Silver)

농부 존은 남는 시간에 MooTube라는 동영상 공유 서비스를 만들었다. MooTube에서 존의 소들은 재밌는 동영상을 서로 공유한다. 소들은 1번부터 $N$번까지 번호가 붙은 동영상 $N$개를 이미 올려 놓았다 ($1 \le N \le 5000$). 하지만 존은 소가 마음에 들어 할 새 동영상을 어떻게 찾아 주어야 할지 아직 정하지 못했다.

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

존은 두 동영상이 서로 얼마나 가까운지 재는 단위로 USADO를 만들었다. 존은 동영상 쌍 $N-1$개를 직접 골라 각 쌍의 USADO를 계산했다. 동영상 하나를 정점으로, 고른 쌍 하나를 연결로 보면 동영상 $N$개는 하나의 네트워크가 되고, 어떤 동영상에서 다른 동영상으로 가는 경로가 정확히 하나씩 존재한다. 존은 두 동영상 사이의 USADO를 그 경로에 놓인 연결의 USADO 중 최솟값으로 정했다.

존은 동영상 하나와 값 $K$를 정한 다음, 그 동영상과의 USADO가 $K$ 이상인 동영상을 모두 추천한다. 그런데 추천이 너무 많으면 소가 일을 못 할까 봐 걱정이다. 그래서 $K$를 적당한 값으로 정하려고 한다. 존이 던지는 질문마다 추천되는 동영상이 몇 개인지 답하라.

첫째 줄에 $N$과 $Q$가 주어진다 ($1 \le Q \le 5000$).

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

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

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

첫 번째 예제를 보자. 1번과 2번 동영상의 USADO는 3, 2번과 3번은 2, 2번과 4번은 4다. 그래서 1번과 3번의 USADO는 $\min(3, 2) = 2$, 1번과 4번은 $\min(3, 4) = 3$, 3번과 4번은 $\min(2, 4) = 2$가 된다.

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