31038번 - 정기 모임 5 스페셜 저지

문제

정점이 $N$개인 트리가 주어진다. 각 정점은 1ドル$번부터 $N$번까지 차례대로 번호가 부여되어 있다. $i$번째 간선은 $A_i$번 정점과 $B_i$번 정점을 연결한다. 트리에서 정점 사이의 거리는 두 정점 사이에 존재하는 유일한 단순 경로에 포함되는 간선의 수로 정의한다. 같은 정점 사이의 거리는 0ドル$으로 정의한다. $i$번 정점에는 $i$번 사람이 살고 있다. 각 정점에 사는 모든 사람들이 모이려고 한다. 이를 위해 다음 조건을 모두 충족하는 길이 $k$의 수열 $p$를 구성해야 한다.

• 1ドル\leq k<N$
• 1ドル\leq p_i\leq N(1\leq i\leq k)$
• $p_i\neq p_j(1\leq i<j\leq k)$
• 1ドル<i<k$인 모든 $i$에 대해 $p_i>p_{i-1}$와 $p_i<p_{i+1}$ 중 정확히 하나만 성립한다.
• $p_1$부터 $p_k$ 까지 순서대로 $p_i$번 사람이 살고 있는 정점과의 거리가 1ドル$ 이하인 정점을 모두 하나로 합치자. 정점 $v_1, \cdots, v_m$를 하나로 합치는 것은 새로운 정점을 만들어 $v_1, \cdots, v_m$와의 거리 중 가장 작은 거리가 1ドル$인 정점들과 간선으로 연결하고, 정점 $v_1, \cdots, v_m$ 그리고 정점 $v_1, \cdots, v_m$와 연결된 모든 간선을 삭제하는 것으로 정의한다. 이 과정에서 합쳐지는 정점에 살던 사람들은 합쳐진 정점으로 이주한다. 최종적으로 모든 사람이 살고 있는 정점이 같아야 한다.

가능한 $k$의 최솟값과 $p$를 출력해야 한다. 길이가 최소인 수열 $p$가 여러 개 존재하면 아무거나 출력해도 된다. 존재하지 않는다면 "IMPOSSIBLE"을 따옴표 없이 출력한다.

입력

첫 번째 줄에 $N$이 주어진다. 이후 $N-1$줄에 걸쳐 $i+1$번째 줄에 트리의 $i$번째 간선을 나타내는 $A_i, B_i$가 공백을 사이에 두고 주어진다. $(1 \le A_i, B_i \le N)$

출력

가능한 수열이 존재하는 경우 $k$의 최솟값과 수열 $p$를 출력하라. 가능한 수열이 존재하지 않는 경우 "IMPOSSIBLE"을 따옴표 없이 출력한다.

제한

• 2ドル\leq N\leq 3\times10^5$
• 1ドル\leq k<N$
• 주어지는 모든 수는 정수이다.

힌트