Given a connected graph with n vertices and n-1 edges, count how many d-nice triplets of vertices it has for every d, 1 \le d \le n - 1. A d-nice triplet is a set of 3 distinct vertices (u, v, w), such that dist(u, v) = dist(v, w) = dist(w, u) = d. dist(a, b) is the length of the shortest path between vertices a and b.

Input

The first line of input contains one integer, n, number of vertices. Next n-1 lines each contain two integers, a_i and b_i, meaning that there is an edge between vertices a_i and b_i.

Output

Output n-1 integers. For each d, 1 \le d \le n-1 output how many d-nice triplets the graph has.

Constraints

• 1 \le n \le 4000

Examples

Input:

4
1 2
1 3
1 4

Output:

0 1 0

Set (2, 3, 4) is a 2-nice triplet.

Input:

8
1 2
2 3
2 4
4 5
5 6
4 7
7 8

Output:

0 2 0 2 0 0 0