In an undirected tree, a node with a degree of 2 is called a "fake node," and all other nodes are called "true nodes." The "simplified tree" of an undirected tree consists of all the true nodes of the original tree. An edge exists between two true nodes in the simplified tree if and only if they are connected by an edge in the original tree, or if there is a path between them in the original tree where all intermediate nodes are fake nodes. Two undirected trees are said to be "substantially isomorphic" if their respective simplified trees are isomorphic—that is, there exists a one-to-one correspondence between the nodes such that any two nodes in one tree are connected by an edge if and only if their corresponding nodes in the other tree are connected by an edge. Given several undirected trees, keep only one from each set of substantially isomorphic trees and remove the others. Count the number of remaining non-substantially isomorphic trees and output the number of nodes in their simplified trees in non-decreasing order.

Input

The first line contains a single positive integer $m$, followed by $m$ undirected trees. For each tree, the first line contains the number of nodes $n$ (nodes are labeled from $1$ to $n$), followed by $n-1$ lines each containing two distinct integers between $1$ and $n$ separated by a space, representing an undirected edge between these two nodes. There are no empty lines between trees.

Output

The first line outputs a positive integer $m_0$ ($1 \le m_0 \le m$), representing the number of non-substantially isomorphic trees. The second line contains $m_0$ positive integers in non-decreasing order, representing the number of nodes in the simplified trees of these $m_0$ trees, separated by spaces.

Constraints

• 30% of the data: $2 \le m \le 10$, $2 \le n \le 10$
• 60% of the data: $2 \le m \le 20$, $2 \le n \le 300$
• 100% of the data: $2 \le m \le 20$, $2 \le n \le 10000$

Examples

Input 1

2
4
1 4
2 4
3 4
5
1 3
2 3
3 4
4 5

Output 1

1
4