G. Гарри против Волан-де-Морта
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После того, как Гарри уничтожил все крестражи Волан-де-Морта, началась их решающая битва. Они кидают друг в друга заклинания, исходящие из волшебных палочек, и заклинания сталкиваются.

Битва происходит в Хогвартсе, который можно представить в виде дерева. В Хогвартсе есть n локаций, соединённых n - 1 двунаправленной дорогой.

Рону, наблюдающему за битвой между Гарри и Волан-де-Мортом, стало интересно, сколько существует троек локаций (u, v, w), таких что если Гарри находится в локации u, а Волан-де-Морт в локации v, их заклинания могут столкнуться в локации w. Это возможно только если u, v и w попарно различны и существуют путь из u в w и путь из v в w, не проходящие по одной и той же дороге.

В хаосе битвы в Хогвартсе стали появляться новые дороги. Вам необходимо вычислять величину, интересующую Рона, после каждого добавления дороги.

Формально, задано дерево из n вершин и n - 1 ребер. q новых рёбер добавляются между вершинами дерева. После каждого добавления необходимо вычислять число троек вершин (u, v, w), таких что u, v и w попарно различны и существуют два пути, один из которых между вершинами u и w, а другой — между v и w, такие, что у них нет общих рёбер.

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

В первой строке содержится целое число n (1 ≤ n ≤ 105) — количество локаций в Хогвартсе.

В каждой из следующих n - 1 строках содержатся два целых числа u и v (1 ≤ u, v ≤ n), показывающие наличие дороги между локациями u и v. Гарантируется, что данный граф является деревом.

В следующей строке задано целое число q (1 ≤ q ≤ 105) — количество новых дорог, добавляемых в граф.

В каждой из следующих q строк содержатся два целых числа u и v, обозначающие новую добавленную дорогу (1 ≤ u, v ≤ n).

Обратите внимание, некоторые новые дороги могут соединять те же локации, что и ранее существующие дороги, или соединять локацию саму с собой.

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

В первой строке выведите число троек до всех добавлений.

После этого выведите q строк, в каждой из которых выведите число ansi, показывающее число троек после i-го запроса о добавлении дороги.

Примеры
Входные данные
3
1 2
2 3
1
2 3
Выходные данные
2
4
Входные данные
4
1 2
2 3
2 4
2
1 4
3 4
Выходные данные
6
18
24
Входные данные
5
1 2
2 3
3 4
4 5
1
1 5
Выходные данные
20
60
Примечание

В первом примере для изначального дерева только (1, 3, 2) и (3, 1, 2) являются возможными тройками локаций (u, v, w).

После добавления ребра из 2 в 3, возможны тройки локаций (1, 3, 2), (3, 1, 2), (1, 2, 3) и (2, 1, 3).