МууТуб (Срібло)

Вхідні дані

Перший рядок містить два цілих числа $n$ та $q (1 \leq n, q \leq 5000)$ q~(1 \leq n, q \leq 5000) — кількість відео та кількість запитів відповідно.

Наступні $n - 1$ n-1 рядків описують пари відео, які фермер Джон оцінює вручну. Кожен рядок містить три цілих числа $p_{i}, q_{i}$ p_i, q_i та $r_{i} (1 \leq p_{i}, q_{i} \leq n, 1 \leq r_{i} \leq 1 0^{9})$ r_i~(1 \leq p_i, q_i \leq n, 1 \leq r_i \leq 10^9), що означає: відео з номерами $p_{i}$ p_i та $q_{i}$ q_i з'єднані ребром зі ступенем відповідності $r_{i}$ r_i.

Далі йдуть $q$ рядків, кожен із яких описує один запит від фермера Джона. У $i$ -му рядку зазначено два числа $k_{i}$ k_i та $v_{i} (1 \leq k_{i} \leq 1 0^{9}, 1 \leq v_{i} \leq n)$ v_i~(1 \leq k_i \leq 10^9, 1 \leq v_i \leq n) — це означає, що у $i$ -му запиті фермер Джон хоче дізнатися, скільки відео буде рекомендовано для відео з номером $v_{i}$ v_i, якщо мінімально допустима відповідність для рекомендації це $k = k_{i}$ k = k_i.

Вихідні дані

Виведіть $q$ рядків. У $i$ -му рядку виведіть відповідь на $i$ -й запит фермера Джона.

Приклади

Фермер Джон встановив такі зв'язки між відео:

Відео $1$ і $2$ мають відповідність $3$ ,
Відео $2$ і $3$ — відповідність $2$ ,
Відео $2$ і $4$ — відповідність $4$ .

За цими даними можна обчислити відповідність між іншими парами відео:

Відео $1$ і $3$ : відповідність = $min (3, 2) = 2$ min(3, 2) = 2,
Відео $1$ і $4$ : відповідність = $min (3, 4) = 3$ min(3, 4) = 3,
Відео $3$ і $4$ : відповідність = $min (2, 4) = 2$ min(2, 4) = 2.

Тепер розглянемо, які відео будуть рекомендовані для наступних запитів:

З відео $2$ при $k = 1$ k = 1 будуть рекомендовані відео $1, 3, 4$ .
З відео $1$ при $k = 3$ k = 3 будуть рекомендовані відео $2$ і $4$ .
З відео $1$ при $k = 4$ k = 4 не буде рекомендовано жодного відео.

Приклад 1

Loading