У Тимофея в саду растёт яблоня, она представляет собой корневое дерево из \(n\) вершин с корнем в вершине \(1\) (вершины пронумерованы от \(1\) от \(n\)). Деревом называется связный граф без циклов, петель и кратных ребер.
Это дерево очень необычное — оно растёт корнем вверх. Впрочем, в этом нет ничего необычного для деревьев в программировании.
Яблоня достаточно молодая, поэтому на ней вырастет всего два яблока. Яблоки вырастут в определённых вершинах (эти вершины могу совпадать). После того как яблоки вырастут, Тимофей начнёт трясти яблоню, пока яблоки не упадут. Каждый раз, когда Тимофей трясёт яблоню, с каждым из яблок происходит следующее:
Пусть яблоко сейчас находится в вершине \(u\).
- Если у вершины \(u\) есть ребёнок, то яблоко перемещается в него (если таких вершин несколько, то яблоко может переместиться в любую из них).
- Иначе яблоко падает с дерева.
Можно показать, что через конечное время оба яблока упадут с дерева.
У Тимофея есть \(q\) предположений, в каких вершинах могут вырасти яблоки. Он предполагает, что яблоки могут вырасти в вершинах \(x\) и \(y\), и хочет узнать количество пар вершин (\(a\), \(b\)), с которых яблоки могут упасть с дерева, где \(a\) — вершина, с которой упадёт яблоко из вершины \(x\), \(b\) — вершина, с которой упадёт яблоко из вершины \(y\). Помогите ему это сделать.
Выходные данные
Для каждого запроса Тимофея выведите количество упорядоченных пар вершин, с которых яблоки могут упасть с дерева, если предположение окажется верным, в отдельной строке.
Примечание
В первом примере:
- Для первого запроса существует две возможные пары вершин, с которых яблоки могут упасть: \((4, 4), (5, 4)\).
- Для второго запроса также существует две пары: \((5, 4), (5, 5)\).
- Для третьего запроса есть всего одна пара: \((4, 4)\).
- Для четвертого запроса существует \(4\) пары: \((4, 4), (4, 5), (5, 4), (5, 5)\).
Дерево из первого примера. Во втором примере для первого предположения есть \(4\) возможных пар вершин, с которых могут упасть яблоки: \((2, 3), (2, 2), (3, 2), (3, 3)\). Для второго запроса есть всего одна возможная пара: \((2, 3)\). Для третьего запроса есть две пары: \((3, 2), (3, 3)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
5
1 2
3 4
5 3
3 2
4
3 4
5 1
4 4
1 3
3
1 2
1 3
3
1 1
2 3
3 1
|
2
2
1
4
4
1
2
|
|
2
|
2
5
5 1
1 2
2 3
4 3
2
5 5
5 1
5
3 2
5 3
2 1
4 2
3
4 3
2 1
4 2
|
1
2
1
4
2
|