마지막 잎새

문제

$N$개의 정점으로 이루어진 트리가 주어진다. 각 정점은 $1$부터 $N$까지 번호가 매겨져 있다. 이때, 리프 노드를 출력하는 프로그램을 작성해 보자.

무슨 소리인지 모르겠다면 아래 힌트를 참고하자.

입력

첫째 줄에 정점의 개수 $N(1 ≤ N ≤ 20\,000)$가 주어진다.

둘째 줄부터 $N - 1$개의 줄에 걸쳐 간선 정보가 $u\ v$의 형태로 주어진다. $u$와 $v$를 잇는 양방향 간선이 존재한다는 의미다.

출력

리프 노드의 번호를 오름차순으로 정렬하여 공백으로 구분하여 출력한다.

예제 입력 1

5
1 2
2 3
2 4
1 5

예제 출력 1

3 4 5

예제 입력 2

6
5 1
4 2
5 2
2 3
6 5

예제 출력 2

1 3 4 6

힌트

그래프란 정점과 두 정점을 잇는 간선으로 이루어진 집합이다.

위 그림은 $7$개의 정점(원 모양)과 $8$개의 간선(실선)으로 이루어진 그래프를 시각화한 그림이다. 원 내부의 수는 각 정점의 구별을 위해 임의로 매긴 것이다. 편의상 원 내부의 수가 $X$인 정점을 $X$번 정점이라 하겠다.

간선은 항상 두 정점을 잇게 된다. 위 그림에서 $1$번 정점과 $3$번 정점을 잇는 간선은 존재하지만, $6$번 정점과 $5$번 정점을 잇는 간선은 존재하지 않는다.

정점의 차수(Degree)란 해당 정점과 연결된 간선의 개수를 의미한다. $2$번 정점의 차수는 $1$이고, $3$번 정점의 차수는 $3$이다.

그래프에서 경로(Path)란 서로 연결된 정점을 나열한 것을 의미한다. 위 그림에서 $1-3-4-7$과 $5-3-1-5$는 경로지만, $2-4$는 경로가 아니다.

그래프에서 사이클(Cycle)이란 임의의 한 정점에서 시작해서, 시작 정점을 제외한 어떤 정점도, 어떤 간선도 $2$번 이상 지나가지 않고 시작점으로 되돌아올 수 있는 경로를 말한다. 위 그림에서 $3-5-1-3$과 $1-6-7-4-3-1$인 사이클이 존재한다. $2-6-2$는 같은 간선을 $2$번 이상 사용했으므로 사이클이 아니고, $2-6-1$은 시작 정점으로 돌아오는 경로가 아니므로 역시 사이클이 아니다.

만약 그래프에 사이클이 단 하나라도 존재하지 않는다면, 그 그래프는 트리(Tree)라고 부른다. 위 그래프는 트리가 아니지만, 간선 몇 개를 제거해서 아래 그림과 같이 트리로 만들 수 있다.

트리의 가장 큰 특징은 바로, 임의의 두 정점을 잇는 경로가 유일하다는 것이다. 이 그림에서 $1$번 정점과 $2$번 정점을 잇는 경로는 $1-6-2$이며, 이는 유일하다.

또한, 간선의 개수는 항상 정점의 개수보다 하나 작다. 위 그림(트리)에서 정점은 총 $7$개인데, 간선은 $6$개인 것을 확인할 수 있다. 간선의 개수가 정점의 개수보다 같거나 크다면 해당 그래프에는 반드시 사이클이 존재하기 때문이고, 정점의 개수보다 둘 이상 작게 되면 연결하지 못하는 정점이 생기기 때문이다. 이들에 대한 자세한 증명은 직접 해보자.

트리의 어떤 정점의 차수가 $1$이라면 그 정점은 리프(Leaf) 노드다. 이제 무엇을 해야할 지 알았을 것이다. 자, 문제를 해결해보자!