풍성한 트리

면접 대비

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

요약

주어진 트리에서 모든 노드의 차수가 1 또는 3이고 모든 리프가 루트에서 같은 거리에 있는지 판별하며, 가능한 루트를 모두 출력합니다.

난이도: 보통10점 중 6점
유형: 트리, 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
```