Во время отдыха, Фермер Джон создал новый видео-сервис, который он назвал
MooTube. На MooTube коровы ФД могут записывать видео, делится ими, и открывать
новые интересные видео. Его коровы уже разместили \(N\) видео (\(1 \leq N \leq 100,000\)),
последовательно пронумерованных \(1 \ldots N\).
ФД хочет создать список "предлагаемых видео" для каждого видео на MooTube,
который будет рекомендовать видео, наиболее релевантные тем, которые коровы
посмотрели.
ФД ввёл "метрику релевантности", которая определяет насколько релевантны два
видео друг другу. Он выбрал \(N-1\) пар видео и вручную вычислил их релевантность.
Затем ФД визуализировал свои видео в виде сети, где каждое видео-вершина, а рёбра
проведены между парами вершин-видео, для которых он проводил анализ релевантности.
Оказалось, что ФД выбрал пары так, что любое видео достижимо от любого другого
по этим рёбрам, причём единственным способом. Теперь ФД определил релевантность
любой пары видео как минимум из релевантностей рёбер на пути от одного видео к
другому.
ФД теперь хочет выбрать такое значение величины \(K\), чтобы при просмотре видео
предлагались к просмотру как релевантные как минимум ещё \(K\) видео.
Однако он боится, что большое \(K\) снизит надои. Поэтому он просит Вас ответить на
вопросы по поводу \(K\).
ФОРМАТ ВВОДА (файл mootube.in):
Первая строка ввода содержит
\(N\) и
\(Q\) \(Q\) (
\(1 \leq Q \leq 100,000\)).
Каждая из следующих \(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\) and \(v_i\)
(\(1 \leq k_i \leq 1,000,000,000, 1 \leq v_i \leq N\)),
указывающих, что \(i\)-ый вопрос ФД таков "сколько видео будет предложено, тому кто
смотрит видео \(v_i\), если \(K = k_i\)."
ФОРМАТ ВЫВОДА (файл file mootube.out):
Выведите \(Q\) строк. На строке \(i\) выведите ответ на \(i\)-ый запрос ФД.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
1 2 3
2 3 2
2 4 4
1 2
4 1
3 1
|
3
0
2
|