Дано дерево из \(n\) вершин с корнем в вершине \(1\). Гуляя по нему со своим котом Чефиром, Сакурако отвлеклась, и Чефир убежал.
Чтобы помочь Сакурако, Косукэ записал свои \(q\) предположений. В \(i\)-м предположении он считает, что Чефир потерялся в вершине \(v_i\) и имел \(k_i\) выносливости.
Также для каждого предположения Косукэ считает, что Чефир мог переместиться по рёбрам произвольное число раз:
- из вершины \(a\) в вершину \(b\), если \(a\) является предком\(^{\text{∗}}\) \(b\), выносливость от этого не изменится;
- из вершины \(a\) в вершину \(b\), если \(a\) не является предком \(b\), тогда выносливость Чефира понизится на \(1\).
Если выносливость Чефира равна \(0\), то он не сможет сделать перемещение второго типа.
Для каждого предположения ваша задача — вычислить расстояние до самой дальней вершины, в которую Чефир мог уйти от вершины \(v_i\), имея \(k_i\) выносливости.
Выходные данные
Для каждого теста и для каждого предположения выведите расстояние до самой дальней вершины, в которую Чефир мог пройти от начальной точки \(v_i\) имея \(k_i\) выносливости.
Примечание
В первом примере:
- В первом запросе можно пройти из вершины \(5\) в вершину \(3\) (после этого выносливость уменьшится на \(1\) и станет равна \(0\)), после этого можно пройти в вершину \(4\);
- Во втором запросе из вершины \(3\) имея \(1\) выносливости можно добраться только до вершин \(2\), \(3\), \(4\) и \(5\);
- В третьем запросе из вершины \(2\) имея \(0\) выносливости можно добраться только до вершин \(2\), \(3\), \(4\) и \(5\);
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|