Задача H. Простые пути в дереве

Автор:Тренировки СПбГУ   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Дан неориентированный связный граф из n вершин и n − 1 ребра. Требуется для каждого ребра посчитать суммарную длину простых путей, проходящих через это ребро. Длиной пути здесь называется количество ребер в пути.

Формат входного файла

На первой строке целое число n. Следующие n − 1 строка содержат пары чисел от 1 до n  — ребра графа.

Формат выходного файла

n − 1 строка. i-я строка должна содержать целое число  — ответ для i-го ребра.

Ограничения

2 ≤ n ≤ 300000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5
1 2
2 3
2 4
5 1
13
8
8
9

0.085s 0.026s 15