버스 노선

아래 그림처럼 도시의 도로망은 지점과 도로로 이루어진 트리이다.

<그림 1>

각 지점은 번호가 적힌 원으로 표시되고, 두 지점을 잇는 선은 도로를 뜻한다. 이 도로망은 다음 성질을 가진다.

• 어느 지점에서 출발해도 도로를 따라 모든 다른 지점으로 갈 수 있다.
• 어떤 도로도 두 번 이상 지나지 않고 출발 지점으로 되돌아오는 방법은 없다.
• 한 지점에 연결된 도로의 수는 10개 이하이다.

이제 이 도로망에 여러 개의 버스 노선을 만들려고 한다. 한 버스 노선은 한 종점에서 다른 종점까지 이어지는 단순 경로이다. 종점은 반드시 단말 지점, 즉 연결된 도로가 하나뿐인 지점이어야 한다.

노선을 정할 때는 다음 조건을 모두 만족해야 한다.

• 모든 지점은 적어도 하나의 노선에 포함되어야 한다. 한 지점이 여러 노선에 포함되는 것은 허용된다.
• 모든 도로는 정확히 하나의 노선에 포함되어야 한다. 같은 도로가 두 노선에 동시에 포함될 수는 없다.
• 각 노선의 양 끝은 단말 지점이어야 하며, 노선 안에서 같은 지점이나 같은 도로를 두 번 지나면 안 된다.
• 위 조건을 만족하는 노선들 중 가장 긴 노선의 길이를 가능한 한 작게 해야 한다. 모든 도로의 길이는 1이다.

<그림 1>에서는 세 노선을 만들 수 있고, 가장 긴 노선의 길이는 4가 된다.

다음 그림과 같이 조건을 만족하는 노선을 만들 수 없는 경우도 있다.

<그림 2>

트리 도로망이 주어질 때, 조건을 만족하면서 가장 긴 노선의 길이를 최소화한 버스 노선들을 출력하는 프로그램을 작성하시오.

첫째 줄에 지점의 수 n이 주어진다. (2 <= n <= 500)

다음 n - 1개 줄에는 도로 정보가 한 줄에 하나씩 주어진다. 지점 i와 지점 j 사이에 도로가 있다면 i j 또는 j i로 주어진다. 지점 번호는 1부터 n까지의 서로 다른 정수이다.

조건을 만족하는 노선 구성이 존재하면 첫째 줄에 가장 긴 노선의 길이를 출력한다. 둘째 줄에 노선의 개수 m을 출력한다.

이후 m개 줄에는 각 노선을 한 줄에 하나씩 출력한다. 한 노선은 한 종점에서 다른 종점까지 방문하는 지점 번호들을 순서대로 적는다. 지점 번호 사이에는 공백 하나를 둔다.

답이 여러 가지라면 아무 답이나 출력해도 된다.

조건을 만족하는 노선 구성이 존재하지 않으면 첫째 줄에 0을 출력한다.