Изначально среди \(N\) коров ФД есть пары друзей \(N-1\).
(\(2\le N\le 2\cdot 10^5\)) коровы, помеченные \(1\dots N\), образуют дерево. Коровы
один за другим покидают ферму в отпуск. В день \(i\) с фермы уходит \(i\)ая корова.
ферме, а затем все пары друзей \(i\)-й коровы, все еще присутствующие на ферме
становятся друзьями.
Для каждого \(i\) от \(1\) до \(N\), непосредственно перед уходом \(i\)-й коровы, ответьте сколько
существуют таких упорядоченных троек различных коров \((a,b,c)\), что ни одна из \(a,b,c\)
не в отпуске, \(a\) дружит с \(b\), а \(b\) дружит с \(c\)?
ФОРМАТ ВВОДА (ввод поступает с терминала/стандартного ввода):
Первая строка содержит
\(N\).
Следующие строки \(N-1\) содержат два целых числа \(u_i\) и \(v_i\), обозначающие, что коровы
\(u_i\) и \(v_i\) изначально друзья (\(1\le u_i,v_i\le N\)).
ФОРМАТ ВЫВОДА (вывод на терминал / стандартный вывод):
Ответы для \(i\) от \(1\) до \(N\) в отдельных строках.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2
2 3
|
2
0
0
|