Josh, Nils, and Mike are being allocated to various work experience sites!

The town consists of ~N~ different buildings indexed from ~1~ to ~N~, connected by ~N-1~ bidirectional roads such that it is possible to get from any building to any other building using only the roads. The ~i~-th road connects buildings ~u_i~ and ~v_i~. Josh, Nils, and Mike will each be allocated to one of the buildings to undergo work experience there. Note that more than one of them can be allocated to the same building.

After a long day's work, they plan to meet up with each other. First, they will select one of the ~N~ buildings. Then, each of them will walk from their current building to the selected building along the roads, taking the route with the fewest roads possible. Exhausted from all of the work, they will select the building such that the total number of roads traversed by all of them is minimised. If multiple buildings can be selected whilst minimising the total number of roads traversed, then out of those buildings, they will select the building with the lowest index.

However, none of them have been allocated to a building yet. All buildings are understaffed, so any allocation of Josh, Nils, and Mike to the buildings is possible. For each building ~x~, they would like to know the number of different ways to allocate them to the buildings such that they will select and meet up at building ~x~. Two ways are considered different if any of Josh, Nils, or Mike are allocated to different buildings amongst the two ways.

Constraints

~1 \le N \le 2 \times 10^5~

~1 \le u_i, v_i \le N, u_i \ne v_i~

It is guaranteed that any building is reachable from any other building by traversing the roads.

Subtask 1 [10%]

The graph is linear. More specifically, for ~1 \le i < N~, ~u_i = i~ and ~v_i = i+1~.

Subtask 2 [20%]

~1 \le N \le 70~

Subtask 3 [30%]

~1 \le N \le 400~

Note that Subtask 2 must be passed for this subtask to be evaluated.

Subtask 4 [40%]

No additional constraints.

Note that all previous subtasks must be passed for this subtask to be evaluated.

Input Specification

The first line of input contains a single integer, ~N~.

The ~i~-th of the following ~N-1~ lines of input contain two space-separated integers ~u_i~ and ~v_i~, representing that the ~i~-th road connects buildings ~u_i~ and ~v_i~.

Output Specification

Print a single line containing ~N~ space-separated integers. The ~i~-th of these integers should be the number of different ways to allocate Josh, Nils and Mike to the buildings such that they will select and meet up at building ~i~.

Sample Input

5
1 2
2 3
2 4
1 5

Sample Output

31 55 13 13 13

Explanation

Let's consider the scenario where Josh is allocated to building ~1~, Nils is allocated to building ~3~, and Mike is allocated to building ~5~.

If they were to meet up at building ~1~, they would traverse a total of ~3~ roads:

• Josh would not need to move at all, so he would traverse ~0~ roads.
• Nils would take the second road to building ~2~, and then take the first road to building ~1~, traversing ~2~ roads.
• Mike would take the ~4~-th road, arriving at building ~1~ after traversing ~1~ road.

In total, they would traverse ~0 + 2 + 1 = 3~ roads. It can be shown that choosing any other building to meet up at would require a greater total number of traversed roads, so in this scenario, they would select and meet up at building ~1~.

Considering all ~125~ scenarios, it can be shown that:

• In ~31~ scenarios, building ~1~ is selected.
• In ~55~ scenarios, building ~2~ is selected.
• In ~13~ scenarios, building ~3~ is selected.
• In ~13~ scenarios, building ~4~ is selected.
• In ~13~ scenarios, building ~5~ is selected.