Problem Statement

At National Koyaso University, preparations for the school festival are underway again this year.

The campus of Koyaso University has $N$ plazas and $N-1$ roads. Each road connects exactly $2$ plazas. Using the $N-1$ roads, all plazas can be reached from one another. The plazas are numbered from $1$ to $N$, and the roads are numbered from $1$ to $N-1$.

Plaza $i$ has $C_i$ roads connected to it, and their numbers are $E_{i,1},E_{i,2},\ldots ,E_{i,C_i}$.

We are now going to draw as many gear symbols as possible on the campus map. A gear symbol of level $K$ can be drawn by choosing $1$ plaza and $K$ roads connected to it. When drawing several gear symbols on the map, they must not overlap one another. That is, you must not draw $2$ or more symbols centered at the same plaza, and you must not choose the same road $2$ or more times throughout the whole process of drawing the symbols.

Also, it has been decided that all gear symbols drawn on the map must be of the same level. Therefore, for each of $q=1,2,\ldots ,N-1$, find the maximum number of gear symbols of level $q$ that can be drawn.

Constraints

The input satisfies the following constraints.

• $2\leq N \leq 200\, 000$
• $1 \leq E_{i,j} \leq N-1$
• $E_{i,j} \neq E_{i,k}$ $(1 \leq i \leq N , 1 \leq j \lt k \leq C_i)$ That is, the same road is never connected to $1$ plaza $2$ or more times.
• Among the values $E_{i,j}$ $(1 \leq i \leq N, 1 \leq j \leq C_i)$, each of $1,2,\ldots ,N-1$ appears exactly $2$ times.
• All plazas can be reached from one another.
• All input values are integers.

Input

$N$
$C_1$ $E_{1,1}$ $E_{1,2}$ $\cdots$ $E_{1,C_1}$
$C_2$ $E_{2,1}$ $E_{2,2}$ $\cdots$ $E_{2,C_2}$
$\vdots$
$C_N$ $E_{N,1}$ $E_{N,2}$ $\cdots$ $E_{N,C_N}$

Output

Output the answers for $q=1,2,\ldots ,N-1$ in this order, separated by spaces.

Print a newline at the end.

Sample

3
1 1
2 2 1
1 2

2 1

Sample 2

Input

15
1 5
1 2
1 7
1 10
2 3 13
1 6
3 9 14 1
1 8
1 11
2 12 4
3 11 9 5
4 12 10 1 6
3 14 2 7
2 4 13
2 3 8

Output

14 6 3 1 0 0 0 0 0 0 0 0 0 0

The $4$ figures below show, for gear symbols of levels $1,2,3,4$ respectively, how to draw the maximum number of symbols.