25924번 - Darkest Dungeon 서브태스크스페셜 저지

연세대학교는 신촌 근처에서 유적을 발견했다. 그 유적에 있는 유물과 보물의 값어치는 상당히 높기에 연세대학교에서 이를 찾아내려고 한다. 그 때문에 위의 이상한 공고문을 통해서 유적 탐색가를 모집하려고 한다.

유적은 $N$개의 방과 $(N-1)$개의 양방향 통로로 구성되어 있으며, 각 방은 $1$번부터 $N$번까지의 번호가 붙어있다. 그리고 유적 내의 서로 다른 두 방 사이에는 반드시 하나의 단순 경로가 존재하고, 그 단순 경로는 유일하다.

탐색가는 한 번의 탐색을 통해서 최대한 많은 방을 탐색하려고 한다. 그러나 유적의 통로에는 기어 다니는 괴물들이 서식하고 있고, 이들은 실제로 사람들을 공격하기 때문에 매우 위험하다. 따라서 통로를 지나가는 동안 괴물들이 싫어하는 횃불을 들고 다녀야 한다. 그러나 유적의 통로를 $K$번 통과하면 횃불이 꺼지기에 탐색가는 한 번의 탐색에서 $K$번 넘게 통로를 통과할 수 없다. 각 방과 통로의 방문 횟수는 따로 제한이 없지만, 같은 방을 두 번 이상 탐색하는 것은 한 번 탐색한 것으로 취급할 것이다.

탐색가는 원하는 방에서부터 탐색을 시작할 수 있고, 본인이 원할 때 탐색을 마치고 유적 밖으로 나갈 수 있다. 이때, 최대한 많은 방을 탐색할 수 있도록 유적을 탐색해보자.

$N$과 $K$는 각각 방의 개수와 통로를 통과할 수 있는 횟수를 의미한다.

$u_i$와 $v_i$는 $u_i$번 방과 $v_i$번 방 사이에 통로가 있음을 의미한다. ($1 \le i \le N-1$)

첫 번째 줄에는 탐색할 수 있는 방 개수의 최댓값을 출력한다.

두 번째 줄에는 최대한 많은 방을 탐색할 수 있는 경로의 통로 통과 횟수 $L$을 출력한다. 단, $L$은 $K$를 넘을 수 없다.

세 번째 줄에는 탐색가가 탐색을 시작한 방의 번호를 출력한다.

네 번째 줄부터 $L$개의 줄에 걸쳐서 탐색한 방의 번호를 순차적으로 출력한다.

최대한 많은 방을 탐색할 수 있는 경로가 여러 개인 경우 아무거나 출력하면 된다.

• $3 \le N \le 500\,000$
• $1 \le K \le 2(N-1)$
• $1 \le u_i, v_i \le N$, $u_i \ne v_i$
• 입력에 주어진 수들은 전부 정수다.