У Li Hua есть дерево из \(n\) вершин и \(n-1\) рёбер. Вершины пронумерованы от \(1\) до \(n\).
Пара вершин \((u,v)\) (\(u < v\)) считается милой, если ровно одно из следующих двух утверждений истинно:
- \(u\) является вершиной с минимальным индексом среди всех вершин на пути \((u,v)\).
- \(v\) — вершина с максимальным индексом среди всех вершин на пути \((u,v)\).
Будет выполнено \(m\) операций. В каждой операции Li Hua выбирает целое число \(k_j\), затем вставляет в дерево вершину с номером \(n+j\), соединяющуюся с вершиной номер \(k_j\).
Он хочет подсчитать количество милых пар вершин до операций и после каждой операции.
Предположим, что вы Li Hua. Пожалуйста, решите эту задачу.
Выходные данные
Выведите \(m+1\) целых чисел — количество милых пар вершин до операций и после каждой операции.
Примечание
Начальное дерево показано на следующем рисунке:
Существует \(11\) милых пар — \((1,5),(2,3),(2,4),(2,6),(2,7),(3,4),(3,6),(3,7),(4,5),(5,7),(6,7)\).
Аналогично, мы можем посчитать милые пары после каждой операции, и результатами будут \(15\) и \(19\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
2 1
1 3
1 4
4 6
4 7
6 5
2
5
6
|
11
15
19
|