삼각별 찾기

양의 정수 $K$에 대해, 크기가 $K$인 삼각별은 하나의 가운데 정점에서 시작하는 길이 $K$의 단순 경로 $3$개가 가운데 정점만 공유하고 뻗어 나가는 모양이다.

정확히는, 트리의 정점 $c$를 가운데 정점으로 하는 크기 $K$의 삼각별이 존재한다는 것은 $c$에서 시작하는 길이 $K$의 단순 경로 $3$개를 고를 수 있고, 이 세 경로가 정점 $c$를 제외한 어떤 정점도 공유하지 않는다는 뜻이다.

$N$개의 정점을 가진 트리가 입력으로 주어진다. 주어진 트리 위에서 찾을 수 있는 서로 다른 삼각별의 개수를 크기별로 구하여라.

두 삼각별의 크기가 같고 가운데 정점이 같다면 같은 삼각별로 본다. 즉, 같은 가운데 정점과 같은 크기에 대해 가능한 경로 $3$개의 선택 방법이 여러 가지여도 하나만 센다.

입력은 다음과 같은 형식으로 주어진다.

$N$ $U_1\ V_1$ $U_2\ V_2$ $\vdots$ $U_{N-1}\ V_{N-1}$

크기가 각각 $1,2,3,\ldots,N$인 서로 다른 삼각별의 개수를 공백으로 구분하여 출력한다.

• $1 \le N \le 100\,000$.
• $1 \le U_i,V_i \le N$ ($1 \le i \le N-1$).
• 주어지는 그래프는 트리이다.