나무 위의 새들

겨울이 찾아오자 여새들은 먹이를 찾아 남쪽으로 날아가기 시작했다. 여새 Siri는 새 $M$마리로 이루어진 무리의 대장이다. 무리는 매년 찾아가는 마가목을 향해 가고 있다. 이 나무는 $N$개의 정점과 일부 정점 쌍을 연결하는 $N-1$개의 간선으로 이루어진 그래프이다. 여러 해에 걸쳐 Siri는 인덱스가 $K$인 정점에 마가목 열매가 유난히 많다는 사실을 알아냈고, 따라서 자신이 정점 $K$에 위치하도록 무리가 착지하게 하고 싶다. 하지만 사람들이 식탁에 앉을 때와 마찬가지로, 여새들도 마가목에 착지할 때 따라야 하는 몇 가지 사회적 규칙이 있다.

• 새들은 나무의 서로 다른 정점에 한 마리씩 차례로 착지한다. 착지 순서는 미리 정해져 있으며, Siri는 대장이므로 항상 마지막에 착지한다.

• 첫 번째 새는 아무 정점에나 착지할 수 있지만, 이후의 각 새는 착지할 수 있는 인접 정점이 있는 새들 가운데 가장 최근에 착지한 새와 인접한 정점에 착지해야 한다.

예를 들어 처음 세 마리의 새가 착지했다면, 가능할 경우 네 번째 새는 세 번째 새 옆에 착지해야 한다. 가능하지 않다면, 가능할 경우 두 번째 새 옆에 착지해야 하며, 이런 식으로 계속한다.

당신의 과제는 요구 사항을 만족하면서 Siri가 정점 번호 $K$에 위치하도록 새들이 착지하는 방법을 찾는 것이다.

채점

해답은 여러 테스트 케이스 그룹에 대해 채점된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$12$| 그래프는 선형이다. 즉, 모든 $i < N$에 대해 정점 $i$은 정점 $i+1$과 연결되어 있다.

$2$ |$16$| $N \leq 10$

$3$ |$20$| $N \leq 200$

$4$ |$17$| $N = M$

$5$ |$35$| 추가 제한 없음.

첫째 줄에는 세 정수 $N$, $M$, $K$가 주어진다($2 \leq M \leq N \leq 10^5$, $1 \leq K \leq N$). 이어지는 $N-1$개의 줄에는 두 정수 $u$와 $v$이 주어지며($1 \leq u,v \leq N$), 이는 인덱스가 $u$와 $v$인 정점이 간선으로 연결되어 있음을 의미한다. 그래프는 트리, 즉 연결되어 있고 사이클이 없는 그래프임이 보장된다.

해가 없다면 $-1$를 출력한다. 그렇지 않다면 $M$개의 정수를 한 줄에 출력하며, $i$:번째 수는 $i$:번째 새가 착지해야 하는 정점의 인덱스이다. 해가 여러 개라면 그중 아무것이나 출력할 수 있다.