Кто не работает, тот не ест. Получи то, что ты хочешь своими силами. Поверь, искренние и серьёзные люди всегда смеются последними. Но я всё равно не дам тебе подарка.
—Санта, Hayate no Gotoku!
Поскольку Хаяте не получил никаких рождественских подарков от Санты, его вместо этого ожидает решение задачи на запросы на дереве.
У Хаяте есть дерево с \(n\) вершинами.
Теперь Хаяте хочет, чтобы вы ответили на \(q\) запросов. Каждый запрос состоит из вершины \(x\) и \(k\) других дополнительных вершин \(a_1,a_2,\ldots,a_k\). Эти \(k+1\) вершина гарантированно различны.
Для каждого запроса необходимо найти длину самого длинного простого пути, начинающегося в вершине \(x^\dagger\) после удаления вершин \(a_1,a_2,\ldots,a_k\) вместе со всеми ребрами, соединенными хотя бы с одной из вершин \(a_1,a_2,\ldots,a_k\).
\(^\dagger\) Простой путь длины \(k\), начинающийся в вершине \(x\) — это последовательность различных вершин \(x=u_0,u_1,\ldots,u_k\) таких, что существует ребро между вершинами \(u_{i-1}\) и \(u_i\) для всех \(1 \leq i \leq k\).
Выходные данные
Для каждого запроса выведите одно целое число, являющееся ответом на этот запрос.
Примечание
В первом примере дерево выглядит следующим образом:
В первом запросе ни одна вершина не пропущена. Самый длинный простой путь, начинающийся в вершине \(2\), это \(2 \to 1 \to 3 \to 4\). Таким образом, ответ — \(3\).
Во третьем запросе отсутствуют вершины \(1\) и \(6\), и дерево показано ниже. Самый длинный простой путь из вершины \(2\) — это \(2 \to 5\). Таким образом, ответ — \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 7
1 2
1 3
3 4
2 5
2 6
6 7
2 0
2 1 1
2 2 1 6
3 1 4
3 1 1
5 0
5 2 1 6
|
3
2
1
4
1
4
1
|
|
2
|
4 4
1 2
1 3
2 4
2 1 3
3 1 4
2 1 4
2 3 1 3 4
|
1
2
2
0
|