МуТуб (Золото)
У вільний час фермер Джон створив нову платформу для обміну відео під назвою MooTube. На MooTube корови фермера Джона можуть записувати, публікувати та переглядати різноманітні кумедні відео. Його корови вже завантажили n відео, пронумерованих від 1 до n. Однак Джон не зовсім розуміє, як допомогти своїм коровам знаходити нові відео, які їм можуть сподобатися.
Джон хоче створити список "рекомендованих відео" для кожного відео на MooTube, щоб корови могли отримувати рекомендації на основі відео, які вони вже переглядають.
Він розробляє метрику "релевантності", яка визначає, наскільки два відео відповідають одне одному. Джон обирає n - 1 пар відео і вручну обчислює їхню попарну відповідність. Потім він візуалізує свої відео як мережу, де кожне відео є вузлом, а n - 1 пар відео, які він розглянув, утворюють зв'язки. Для зручності Джон обрав ці n - 1 пар так, що будь-яке відео можна досягти з будь-якого іншого відео шляхом з'єднань лише одним способом. Джон вирішує, що релевантність будь-якої пари відео повинна визначатися як мінімальна релевантність будь-якого з'єднання на цьому шляху.
Фермер Джон хоче вибрати значення k так, щоб поруч із будь-яким заданим відео на MooTube пропонувалися всі інші відео, які мають релевантність не менше k до цього відео. Однак Джон стурбований тим, що його коровам буде запропоновано занадто багато відео, що може відволікати їх від виробництва молока! Тому він хоче ретельно встановити відповідне значення k. Фермеру Джону потрібна ваша допомога, щоб відповісти на ряд запитань про запропоновані відео для певних значень k.
Вхідні дані
Перша стрічка містить числа n (1 ≤ n ≤ 100000) і q (1 ≤ q ≤ 100000). Наступні n − 1 рядків описують пари відео, які Джон порівнює вручну. Кожен рядок містить три цілі числа p[i], q[i] і r[i] (1 ≤ p[i], q[i] ≤ n, 1 ≤ r[i] ≤ 10^9), що вказує на те, що відео p[i] і q[i] пов'язані з релевантністю r[i].
Наступні q рядків описують q запитів фермера Джона. Кожен рядок містить два цілі числа k[i] і v[i] (1 ≤ k[i] ≤ 10^9, 1 ≤ v[i] ≤ 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 будуть пропонуватися з першого відео.