Farmer John은 여가 시간에 MooTube라는 새 동영상 공유 서비스를 만들었습니다. 소들은 재미있는 동영상을 촬영하고 공유하며 찾아볼 수 있습니다. 이미 $N$개의 동영상($1 \leq N \leq 5000$)을 게시했으며 번호는 $1 \ldots N$입니다. 하지만 FJ는 소들이 좋아할 만한 새 동영상을 찾게 도울 방법을 모르겠습니다.

FJ는 MooTube의 각 동영상에 ‘추천 동영상’ 목록을 만들어 소들이 이미 보는 동영상과 가장 관련 있는 동영상을 추천하려 합니다.

FJ는 이름처럼 두 동영상이 얼마나 관련 있는지 나타내는 ‘관련도’를 정의합니다. $N-1$쌍을 선택해 관련도를 직접 계산합니다. 동영상을 노드로, 직접 살펴본 $N-1$쌍을 연결로 하는 네트워크를 만듭니다. 선택한 $N-1$쌍은 어떤 두 동영상 사이에도 연결을 통한 경로가 정확히 하나가 되도록 합니다. 임의의 두 동영상의 관련도는 그 경로에 있는 연결들의 관련도 중 최솟값으로 정의합니다.

Farmer John은 $K$를 골라 각 MooTube 동영상 옆에 그 동영상과의 관련도가 $K$ 이상인 다른 모든 동영상을 추천하려 합니다. 하지만 너무 많은 추천은 소들이 우유 생산에 집중하지 못하게 할까 걱정합니다! 따라서 적절한 $K$를 신중히 정하려 합니다. 특정 $K$값에서의 추천에 대한 질문들에 답하도록 도와주세요.

입력

첫 줄에는 $N$과 $Q$ ($1 \leq Q \leq 5000$)가 주어집니다.

다음 $N-1$줄은 FJ가 직접 비교한 동영상 쌍을 나타냅니다. 각 줄에는 세 정수 $p_i$, $q_i$, $r_i$ ($1 \leq p_i, q_i \leq N, 1 \leq r_i \leq 1,000,000,000$)가 주어지며 동영상 $p_i$와 $q_i$가 관련도 $r_i$로 연결됨을 나타냅니다.

다음 $Q$줄은 Farmer John의 $Q$개 질문을 나타냅니다. 각 줄에는 두 정수 $k_i$와 $v_i$ ($1 \leq k_i \leq 1,000,000,000, 1 \leq v_i \leq N$)가 주어지며, $i$번째 질문은 $K = k_i$일 때 동영상 $v_i$의 시청자에게 몇 개의 동영상이 추천되는지 묻습니다.

출력

$Q$줄을 출력하세요. $i$번째 줄에 FJ의 $i$번째 질문의 답을 출력합니다.

예제

입력 1

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

출력 1

3
0
2

참고

동영상1과2의 관련도는3, 2와3은2, 2와4는4입니다. 따라서1과3의 관련도는 $min(3, 2) = 2$, 1과4는 $min(3, 4) = 3$, 3과4는 $min(2, 4) = 2$입니다.

Farmer John은 $K=1$일 때 동영상2에서, $K=3$일 때 동영상1에서, $K=4$일 때 동영상1에서 몇 개가 추천되는지 알고 싶습니다. $K=1$이면 동영상2에1,3,4가 추천됩니다. $K=4$이면 동영상1에 아무것도 추천되지 않습니다. $K=3$이면 동영상1에2,4가 추천됩니다.

문제 작성: Jay Leeds