추천 동영상

휴가 동안, 개발자 주환은 JTube라는 새로운 동영상 공유 서비스를 만들었습니다. JTube에서 친구들은 재미있는 동영상을 녹화하고, 서로 공유하며, 발견할 수 있습니다. 이미 친구들은 $N$개의 동영상 ($1 \leq N \leq 5000$)을 게시했고, 이를 편리하게 $1 \ldots N$으로 번호가 매겨졌습니다. 그러나 주환은 친구들이 좋아할 만한 새로운 동영상을 어떻게 찾아주어야 할 지 알아내지 못하고 있습니다.

주환은 모든 JTube 동영상에 대해 '추천 동영상' 목록을 만들고 싶어합니다. 이렇게 하면 친구에게 이미 보고 있던 동영상과 가장 관련이 있는 동영상들을 추천할 수 있게 됩니다.

주환은 '관련성'이라는 척도를 고안하였는데, 이는 두 동영상이 서로 얼마나 관련성이 있는 지를 판단합니다. 그는 $N-1$개의 동영상 쌍을 선택하고 그들 사이의 관련성을 수동으로 계산합니다. 그 다음, 주환은 각 동영상이 노드이고 그가 수동으로 고려하였던 $N-1$개의 동영상 쌍이 연결되어 있는 네트워크로 동영상을 시각화합니다. 편리하게도, 주환은 임의의 동영상이 정확히 하나의 연결 경로를 따라 다른 동영상에 도달할 수 있도록 $N-1$개의 쌍을 선택했습니다. 주환은 두 동영상 간의 관련성은 이 경로상의 모든 연결의 최소 관련성으로 정의되어야 한다고 결정합니다.

주환은 주어진 JTube 동영상 옆에, 그 비디오와의 관련성이 $K$ 이상인 모든 다른 동영상들이 추천되도록 $K$ 값을 설정하려고 합니다. 그러나, 주환은 너무 많은 동영상들이 친구들에게 추천될 수 있을 것을 걱정하고 있는데, 이는 그들의 시험 공부를 방해할 수 있습니다! 따라서 그는 신중하게 $K$ 값의 적합한 수준을 설정하려고 합니다. 주환은 $K$ 값에 따른 추천 동영상에 대한 여러 가지 질문에 대한 답변하는 것을 당신이 도와주는 것을 원합니다.

첫 번째 입력 줄에는 $N$과 $Q$ ($1 \leq Q \leq 5000$)가 포함됩니다.

다음 $N-1$개의 줄은 주환이 수동으로 비교한 동영상 쌍을 각각 설명합니다. 각 줄에는 세 개의 정수 $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$개의 줄은 주환의 $Q$개의 질문을 설명합니다. 각 줄에는 두 개의 정수, $k_i$ 와 $v_i$ ($1 \leq k_i \leq 1,000,000,000, 1 \leq v_i \leq N$)가 포함되어 있으며, 이는 FJ의 $i$번째 질문이 $K = k_i$일 때 비디오 $v_i$를 보는 사람들에게 몇 개의 동영상이 추천될 것인지 묻는다는 것을 의미합니다.

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