Justified Forest Partition

A tree is a graph consisting of \(n\) nodes and \(n-1\) undirected edges in which any two nodes are connected by exactly one path. A forest is a graph consisting of one or more trees. In other words, a graph is a forest if every connected component is a tree. A forest is justified if all connected components have the same number of nodes.

Given a tree \(G\) with \(n\) nodes, you are to find all positive integers \(k\) such that a justified forest can be obtained by erasing exactly \(k\) edges from \(G\). Erasing an edge never erases any nodes. In particular, when we erase all \(n-1\) edges from \(G\), we obtain a justified forest consisting of \(n\) one-node components.

Note that after erasing \(k\) edges, the tree splits into \(k+1\) connected components, and for the forest to be justified each component must contain exactly \(\frac{n}{k+1}\) nodes. Therefore, a necessary condition is that \(k+1\) divides \(n\). However, the structure of \(G\) may not allow such a partition.

Your task is to output all valid \(k\) (in increasing order) for which such a justified forest exists.

inputFormat

The first line contains a single integer \(n\) (\(2 \le n \le 2 \times 10^5\)), representing the number of nodes in the tree. The following \(n-1\) lines each contain two integers \(u\) and \(v\) (\(1 \le u, v \le n\)), representing an undirected edge between nodes \(u\) and \(v\). It is guaranteed that the given graph is a tree.

outputFormat

Output all valid positive integers \(k\) (separated by a space) in increasing order. Each \(k\) satisfies that by erasing exactly \(k\) edges from the tree, a justified forest can be obtained. (Remember that the resulting forest will have \(k+1\) connected components, each with \(\frac{n}{k+1}\) nodes.)

sample

2
1 2

1