문제

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) 노드다. 이제 무엇을 해야할 지 알았을 것이다. 자, 문제를 해결해보자!