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

У вільний час фермер Джон створив нову платформу для обміну відео під назвою MooTube. На MooTube його корови можуть записувати, публікувати та переглядати різноманітні кумедні відео. Корови вже завантажили $n$ відео, пронумерованих від $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$ будуть пропонуватися з першого відео.