Justified Jungle

Time limit6sMemory limit512 MB

Summary

Given a tree with n nodes, find every k such that removing exactly k edges leaves a forest whose connected components all have the same size.

Level: Medium7 of 10
Topics: Tree, DFS, Number theory, Math
Solved: No attempts yet

Problem

A tree is a graph with $n$ nodes and $n-1$ undirected edges in which every two nodes are connected by exactly one path. A forest is a graph made of one or more trees. In other words, a graph is a forest when every connected component is a tree. A forest is justified when all of its connected components hold the same number of nodes.

You are given a tree $G$ with $n$ nodes. Find every positive integer $k$ such that erasing exactly $k$ edges from $G$ leaves a justified forest. Erasing an edge never erases a node. In particular, erasing all $n-1$ edges of $G$ leaves a justified forest of $n$ one-node components.

Input

The first line contains the number of nodes $n$ of $G$ . ( $2 \le n \le 1\,000\,000$ )

The $k$ -th of the next $n-1$ lines contains two different integers $a_k$ and $b_k$ , the endpoints of the $k$ -th edge. ( $1 \le a_k, b_k \le n$ )

Output

On the first line print every wanted $k$ in increasing order. Separate the numbers with single spaces.

Hint

The figures show the justified forests obtained by erasing 1, 3 and 7 edges from the tree in the sample input.

Examples4

Example 1
Input
```
8
1 2
2 3
1 4
4 5
6 7
8 3
7 3
```
Expected output
```
1 3 7
```
Example 2
Input
```
2
1 2
```
Expected output
```
1
```
Example 3
Input
```
6
1 2
2 3
3 4
4 5
5 6
```
Expected output
```
1 2 5
```
Example 4
Input
```
5
1 2
1 3
1 4
1 5
```
Expected output
```
4
```