풍성한 트리

시간 제한1초메모리 제한1024 MB

요약

주어진 트리에서 모든 내부 노드의 차수가 3이고 루트의 차수도 3이며 모든 잎이 같은 깊이에 놓이도록 만드는 루트 후보를 모두 찾는다.

난이도: 어려움10점 중 8점
유형: 트리, DFS, 구현
정답자: 아직 제출이 없습니다

문제

루매는 모든 종류의 트리를 좋아하지만, 그 중에서도 특별히 더 좋아하는 트리가 있다. 루매는 특별히 좋아하는 트리를 '풍성한 트리'라고 정의내렸다. 다음 조건을 만족하는 트리를 '풍성한 트리'라고 한다.

모든 노드의 차수는 $1$ 또는 $3$ 이다. 단, 루트 노드의 차수는 $3$ 이다.
루트 노드와 차수가 $1$ 인 모든 노드간의 거리는 모두 같다.

이 때 두 노드 사이의 거리는 두 노드를 연결하는 단순 경로의 간선 개수로 정의된다. 호기심 많은 루매는 주어진 트리가 '풍성한 트리'인지 여부를 알고 싶다. 또한, 루매는 풍성한 트리의 꼭대기에 앉는 걸 좋아하기에 주어진 트리가 '풍성한 트리' 라면 어떤 노드가 루트 노드가 될 수 있는지 알고 싶다.

입력

첫 번째 줄에 트리의 노드 개수 $N$ 이 주어진다. $(4\leq N\leq 200\ 000)$

두 번째 줄부터 $N-1$ 개의 줄에 걸쳐 노드 $a$ , $b$ 가 공백으로 구분되어 주어진다. $(1\leq a,b \leq N)$ 노드 $a$ 와 노드 $b$ 는 간선으로 이어져 있다.

주어진 입력은 트리임이 보장된다.

출력

주어진 트리가 '풍성한 트리'가 될 수 있다면 첫 번째 줄에 루트 노드가 될 수 있는 노드의 개수를 출력한다. 두 번째 줄에 루트 노드가 될 수 있는 노드를 오름차순으로 공백으로 구분해 모두 출력한다.

만약 주어진 트리가 '풍성한 트리'가 될 수 없다면 $-1$ 을 출력한다.

예제2

예제 1
입력
```
4
1 2
1 3
1 4
```
예상 출력
```
1
1
```
예제 2
입력
```
5
1 2
2 3
3 4
4 5
```
예상 출력
```
-1
```