МуТуб (Серебро)

В свободное время фермер Джон создал новую службу обмена видео, которую назвал MooTube. На MooTube коровы фермера Джона могут записывать, публиковать и открывать для себя множество забавных видео. Его коровы уже разместили $n$ видео с последовательными номерами $\mathrm{1...}n$. Однако ФД не совсем понимает, как помочь своим коровам найти новые видео, которые им могут понравиться.

ФД хочет создать список "рекомендуемых видео" для каждого видео на MooTube. Таким образом, коровам будут рекомендованы видео, наиболее подходящие тем, которые они уже смотрят.

ФД разрабатывает метрику "релевантности", которая определяет насколько два видео соответствуют друг другу. Он выбирает $n-1$ пар видео и вручную вычисляет их попарное соответствие. Затем ФД визуализирует свои видео как сеть, где каждое видео является узлом, а $n-1$ пар видео, которые он вручную рассматривал, связаны. Для удобства ФД выбрал свои $n-1$ пар так, чтобы любое видео могло быть доступно из любого другого видео на пути соединений точно одним способом. ФД решает, что релевантность любой пары видео должна определяться как минимальная релевантность любого соединения на этом пути.

Фермер Джон хочет выбрать значение $k$ так, чтобы рядом с любым заданным видео на MooTube предлагались все другие видео, имеющие релевантность как минимум $k$ к этому видео. Однако ФД обеспокоен тем, что его коровам будет предложено слишком много видео, что может отвлечь их от производства молока! Поэтому он хочет тщательно установить соответствующее значение $k$. Фермеру Джону нужна ваша помощь, чтобы ответить на ряд вопросов о предлагаемых видео для определенных значений $k$.

Входные данные

Первая строка содержит числа $n(1\le n\le 5000)$ и $q(1\le q\le 5000)$. Следующие $n-1$ строк описывают пару видеороликов, которые ФД сравнивает вручную. Каждая строка содержит три целых числа $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$ связаны с релевантностью $r_i$.

Следующие $q$ строк описывают $q$ запросов фермера Джона. Каждая строка содержит два целых числа $k_i$ и $v_i(1\le k_i\le 10^9,1\le v_i\le n)$ — это означает что в $i$-ом запросе ФД спрашивает, сколько видеороликов предложит зрителям видео $v_i$, если $k=k_i$.

Выходные данные

Выведите $q$ строк. В строке $i$ выведите ответ на $i$ - ый вопрос ФД.

Примеры

Фермер Джон обнаруживает, что видео один и два имеют релевантность $3$, видео два и три имеют релевантность $2$, а видео два и четыре имеют релевантность $4$. Исходя из этого, первое и третье видео имеют релевантность $min(3,2)=2$, первое и четвертое видео имеют релевантность $min(3,4)=3$, а видео три и четыре имеют релевантность $min(2,4)=2$.

Фермер Джон хочет знать, сколько видеороликов будет предложено из второго видео, если $k=1$, из первого видео, если $k=3$, и из первого видео, если $k=4$. Мы видим, что при $k=1$ видео $1,3$ и $4$ будут предлагаться на втором видео. Если $k=4$, из первого видео не будут предлагаться видео. Однако при $k=3$ видео $2$ и $4$ будут предлагаться из первого видео.