После того, как Гарри уничтожил все крестражи Волан-де-Морта, началась их решающая битва. Они кидают друг в друга заклинания, исходящие из волшебных палочек, и заклинания сталкиваются.
Битва происходит в Хогвартсе, который можно представить в виде дерева. В Хогвартсе есть 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, такие, что у них нет общих рёбер.
Выходные данные
В первой строке выведите число троек до всех добавлений.
После этого выведите q строк, в каждой из которых выведите число ansi, показывающее число троек после i-го запроса о добавлении дороги.
Примечание
В первом примере для изначального дерева только (1, 3, 2) и (3, 1, 2) являются возможными тройками локаций (u, v, w).
После добавления ребра из 2 в 3, возможны тройки локаций (1, 3, 2), (3, 1, 2), (1, 2, 3) и (2, 1, 3).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2
2 3
1
2 3
|
2
4
|
|
2
|
4
1 2
2 3
2 4
2
1 4
3 4
|
6
18
24
|
|
3
|
5
1 2
2 3
3 4
4 5
1
1 5
|
20
60
|