Bus Routes

A Czech town called Kocourkov has a public transport system. It has $N$ bus stops and $N - 1$ two-way roads, and each road joins two different stops. From any stop you reach every other stop by following roads.

Every morning each stop sends out exactly one bus to every other stop, so there are $N(N - 1)$ buses in total. A bus halts once at every stop on the route from its origin to its destination.

Every stop needs a timetable that lists all the buses halting there. The buses that begin their route at that stop and the buses that end their route there belong on the timetable too.

You are given a description of the transport system in Kocourkov. For every stop, count the buses that halt there.

The first line contains $N$, the number of bus stops. The stops are numbered 1 through $N$. Each of the next $N - 1$ lines describes one road of the town and contains the numbers of the two different stops it joins, $x$ and $y$ ($1 \le x, y \le N$).

$1 \le N \le 10^6$.

Print $N$ lines. Line $i$ contains a single integer, the number of buses that halt at stop $i$.