22967번 - 구름다리 스페셜 저지

선린인터넷고등학교에는 여러 건물과 그 건물들을 연결하는 구름다리가 있다.

구체적으로, $1$번부터 $N$번까지의 번호가 붙은 건물 $N$개와, 서로 다른 두 건물을 잇는 구름다리 $N-1$개가 있다.

모든 건물들은 구름다리들을 통해 직, 간접적으로 연결되어 있다.

2019년도 천하제일 토목건축대회 우승자인 정휘는 구름다리가 너무 적어서 건물 사이를 이동하기 힘들다고 느꼈다.

그래서 정휘는 2018년도 준우승자인 노현이를 고용해 구름다리를 추가로 건설하기로 했다.

노현이는 최대 $N-1$개의 구름다리를 추가로 건설해서, 선린인터넷고등학교의 지름을 최대한 작게 만들어야 한다.

학교의 지름이란, 학교의 두 건물 사이를 구름다리로만 이동할 때 거쳐야 하는 구름다리 개수의 최댓값을 뜻한다.

지름을 최대한 작게 하려면, 구름다리를 어떻게 건설해야 할까?

첫째 줄에 건물의 개수 $N$이 주어진다.

둘째 줄부터 $N-1$개의 줄에 걸쳐, 이미 존재하는 구름다리들이 연결하고 있는 서로 다른 두 건물의 번호가 한 줄에 하나씩 주어진다.

첫째 줄에는 학교의 지름을 최대한 작게 만들기 위해 노현이가 추가로 건설해야 하는 구름다리의 개수 $K$를 출력한다. ($0 \le K \le N-1$)

둘째 줄에는 노현이가 아래에 출력할 방법으로 $K$개의 구름다리를 추가로 건설한 뒤 학교의 지름 $R$을 출력한다.

셋째 줄부터 $K$개의 줄에 걸쳐, 건설할 구름다리들이 연결할 서로 다른 두 건물의 번호를 한 줄에 하나씩 출력한다.

출력하는 구름다리들은 모두 서로 달라야 하며, 이미 존재하는 구름다리를 다시 건설할 수는 없다.

출력한 방법대로 구름다리를 건설했을 때 학교의 지름이 $R$이 되고, 이 값 $R$이 $N-1$개 이하의 구름다리를 건설해서 만들 수 있는 지름의 최솟값과 같다면, 출력은 정답으로 채점된다.

• $2 \leq N \leq 300$
• 동일한 두 건물을 연결하는 구름다리가 여러 개 주어지지 않는다.