G. Сакурако и Чефир
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево из $$$n$$$ вершин с корнем в вершине $$$1$$$. Гуляя по нему со своим котом Чефиром, Сакурако отвлеклась, и Чефир убежал.

Чтобы помочь Сакурако, Косукэ записал свои $$$q$$$ предположений. В $$$i$$$-м предположении он считает, что Чефир потерялся в вершине $$$v_i$$$ и имел $$$k_i$$$ выносливости.

Также для каждого предположения Косукэ считает, что Чефир мог переместиться по рёбрам произвольное число раз:

  • из вершины $$$a$$$ в вершину $$$b$$$, если $$$a$$$ является предком$$$^{\text{∗}}$$$ $$$b$$$, выносливость от этого не изменится;
  • из вершины $$$a$$$ в вершину $$$b$$$, если $$$a$$$ не является предком $$$b$$$, тогда выносливость Чефира понизится на $$$1$$$.

Если выносливость Чефира равна $$$0$$$, то он не сможет сделать перемещение второго типа.

Для каждого предположения ваша задача — вычислить расстояние до самой дальней вершины, в которую Чефир мог уйти от вершины $$$v_i$$$, имея $$$k_i$$$ выносливости.

$$$^{\text{∗}}$$$Вершина $$$a$$$ является предком вершины $$$b$$$, если кратчайший путь от $$$b$$$ к корню проходит через $$$a$$$.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1\le t\le 10^4$$$) — количество наборов входных данных.

Каждый набор входных данных описывается следующим образом:

  • Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество вершин в дереве.
  • Следующие $$$n-1$$$ строки содержат ребра дерева. Гарантируется, что заданные ребра образуют дерево.
  • Следующая строка состоит из одного целого числа $$$q$$$ $$$(1\le q\le 2 \cdot 10^5)$$$, которое обозначает количество предположений Косукэ.
  • Следующие $$$q$$$ строк описывают предположения, которые сделал Косукэ, двумя целыми числами $$$v_i$$$, $$$k_i$$$ $$$(1\le v_i \le n, 0 \le k_i\le n)$$$.

Гарантируется, что сумма $$$n$$$ и сумма $$$q$$$ по всем наборам входных данных не превышает $$$2\cdot 10^5$$$.

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

Для каждого теста и для каждого предположения выведите расстояние до самой дальней вершины, в которую Чефир мог пройти от начальной точки $$$v_i$$$ имея $$$k_i$$$ выносливости.

Пример
Входные данные
3
5
1 2
2 3
3 4
3 5
3
5 1
3 1
2 0
9
8 1
1 7
1 4
7 3
4 9
3 2
1 5
3 6
7
6 0
2 3
6 2
8 2
2 4
9 2
6 3
6
2 1
2 5
2 4
5 6
4 3
3
3 1
1 3
6 5
Выходные данные
2 1 2 
0 5 2 4 5 5 5 
1 3 4
Примечание

В первом примере:

  • В первом запросе можно пройти из вершины $$$5$$$ в вершину $$$3$$$ (после этого выносливость уменьшится на $$$1$$$ и станет равна $$$0$$$), после этого можно пройти в вершину $$$4$$$;
  • Во втором запросе из вершины $$$3$$$ имея $$$1$$$ выносливости можно добраться только до вершин $$$2$$$, $$$3$$$, $$$4$$$ и $$$5$$$;
  • В третьем запросе из вершины $$$2$$$ имея $$$0$$$ выносливости можно добраться только до вершин $$$2$$$, $$$3$$$, $$$4$$$ и $$$5$$$;