Bountiful Tree

Interview

Time limit1sMemory limit1024 MB

Summary

Given a tree, decide whether every node has degree 1 or 3 and all leaves are equally far from the root, then list all valid roots.

Level: Medium6 of 10
Topics: Tree, DFS, Implementation
Solved: No attempts yet

Problem

Rumae likes every kind of tree, but one kind is her favorite. She calls a tree that meets the following conditions a 'bountiful tree'.

Every node has degree $1$ or $3$ . The root node has degree $3$ .
The distance from the root node to every node with degree $1$ is the same.

The distance between two nodes is the number of edges in the simple path connecting them. Curious Rumae wants to know whether a given tree is a 'bountiful tree'. Rumae also likes to sit at the top of a bountiful tree, so if the given tree is a 'bountiful tree', she wants to know which nodes can be the root.

Input

The first line contains the number of nodes $N$ of the tree. ( $4\leq N\leq 200\ 000$ )

The next $N-1$ lines each contain two nodes $a$ and $b$ , separated by a space. ( $1\leq a,b \leq N$ ) Node $a$ and node $b$ are connected by an edge.

The input is guaranteed to be a tree.

Output

If the given tree can be a 'bountiful tree', print on the first line the number of nodes that can be the root. On the second line, print all such nodes in ascending order, separated by spaces.

If the given tree cannot be a 'bountiful tree', print $-1$ .

Examples2

Example 1
Input
```
4
1 2
1 3
1 4
```
Expected output
```
1
1
```
Example 2
Input
```
5
1 2
2 3
3 4
4 5
```
Expected output
```
-1
```