나무 위의 고양이

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

요약

가지 연결 정보가 담긴 나무와 고양이가 앉은 가지 K가 주어질 때, K에서 뿌리까지 이어지는 경로를 출력합니다.

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

문제

아이쿠! 고양이 한 마리가 나무에 갇혔다. 다행히 나무의 가지에는 번호가 붙어 있다. 나무의 구조와 고양이가 앉은 위치가 주어질 때, 고양이가 땅으로 내려오도록 돕는 프로그램을 작성해 줄 수 있는가?

입력

입력은 나무 하나에 대한 설명이다. 첫 줄에는 고양이가 갇힌 가지의 번호를 나타내는 정수 $K$ 가 주어진다. 이후 각 줄에는 두 개 이상의 정수 $a, b\_1, b\_2, \ldots$ 가 주어진다. 이 줄은 가지가 갈라지는 관계를 나타내며, 고양이는 내려가는 길에 $b\_1, b\_2, \ldots$ 에서 $a$ 로 갈 수 있다. 따라서 $a$ 는 모든 $b\_i$ 보다 뿌리에 가깝다. 입력의 마지막 줄은 -1이다. 각 가지 $b\_i$ 는 정확히 한 줄에만 나타난다. 가지 번호는 1부터 100 사이의 정수이지만, 연속적이지 않을 수 있다. 주어진 모든 가지에서 뿌리까지 가는 경로가 있음이 보장된다. 고양이가 앉은 가지의 번호는 뿌리의 번호와 다르다.

출력

고양이가 앉은 가지부터 시작해 땅까지 가는 경로를 출력한다.

예제1

예제 1

입력

14
25 24
4 3 1 2
13 9 4 11
10 20 8 7
32 10 21
23 13 19 32 22
19 12 5 14 17 30
14 6 15 16
30 18 31 29
24 23 26
26 27 28
-1

예상 출력

14 19 23 24 25