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