¿La página no carga? Prueba haciendo clic aquí.
Placeholder

#7096

고양이 구하기 1s 1024MB

Problemas

나무 위에 고양이가 올라가서 내려오는 길을 찾지 못해 울고있다.

다행히도 나무의 가지에는 여기저기 번호가 붙어있기에 고양이가 나무에서 최대한 빠르게 내려오는 길을 안내해주는 프로그램을 작성해보자.


Entrada

입력은 트리에 대한 설명으로, 첫 번째 줄에는 고양이가 현재 위치한 가지의 번호를 의미하는 정수 K가 주어진다.

두 번째 줄부터 -1이 입력되기 전까지 두 줄씩 첫 줄은 두 개 정수로 아랫 가지의 번호 A와 해당 가지의 위로 연결된 가지들의 개수 A_N이 주어지고, 다음 줄은 A번 가지 위로 연결된 가지들의 번호 B_1,\ ...\ ,B_{A_N}가 주어진다.

따라서, A번 가지는 B_1,\ ...\ ,B_{A_N}번 가지들보다 뿌리에 더 가깝다.

모든 가지의 번호는 1...100 범위의 정수다.

가지의 번호들은 반드시 연속적이지는 않지만, 나열된 모든 가지에서 루트로 가는 경로가 있다는 것이 보장된다.

고양이는 뿌리가 아닌 다른 가지에 앉을 것이다.


Salida

고양이가 가장 빠르게 뿌리에 있는 가지까지 내려오는 경로를 한 줄에 출력한다.


Ejemplo #1

77
100 2
77 88
-1
77 100

Ejemplo #2

3
7 1
8
9 2
1 10
3 1
4
10 1
3
5 3
6 9 7
-1
3 10 9 5

Ejemplo #3

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

문제에 주어진 이미지에 대한 예제다.



Fuente

2015 Virginia Tech High School Programming Contest
Debes iniciar sesión para escribir código.