2634번 - 버스노선 스페셜 저지

문제

<그림 1>은 어떤 도시의 도로망을 나타내고 있다.

<그림 1>

이 도시의 지점은 숫자를 포함하는 동그라미로 표시되어 있고, 두 지점 사이에 있는 도로는 두 지점을 잇는 선으로 표시되어 있다. 이 도로망의 특성은 다음과 같다.

• 특성 1. 임의의 한 지점에서 도로와 지점을 거쳐 모든 다른 지점으로 갈 수 있다.
• 특성 2. 한 지점에서 출발하여 어떤 도로를 두 번이상 거치지 않고는 출발지점으로 되돌아 올 수 없다.
• 특성 3. 한 지점과 접한 도로의 개수는 10이하이다.

위의 세 가지 특성을 만족하는 도로망을 트리도로망이라 한다. 이제 이 도시에서 몇 개의 버스노선을 신설하려고 한다. 각각의 버스노선은 한 종점에서 반대편 종점까지 가는 도로와 지점으로 이루어진다. 종점이 될 수 있는 지점은 도로망에서 단말지점(자신과 연결된 다른 지점이 하나 뿐인 곳)이어야 한다. 예를 들어, <그림 1>에서 버스 종점이 될 수 있는 지점은 색칠된 1, 2, 5, 6, 9, 10번 지점이다.

<그림 1>과 같은 경우에 두 개씩의 단말지점으로 짝을 지어 세 개의 서로 다른 버스노선을 만들 수 있다. 단, 버스 노선을 설정하기 위해서는 다음 조건들을 만족해야 한다.

• 조건 1. 도시의 모든 지점은 반드시 하나의 노선에 포함되어야 하고, 두 개 이상의 버스 노선에 포함 될 수도 있다. 예를 들어, 1-3-8-10 노선과 9-7-8-4-5 노선과 같이 한 교차지점을 공유하는 것은 허용된다.
• 조건 2. 도시의 모든 도로는 하나의 버스노선에는 포함되어야 한다. 그러나 한 도로는 두 개의 버스노선에 포함될 수는 없다. 예로 <그림 1>에서 6-7-8-10이 버스노선인 경우, 9-7-8-4-5는 도로 (7, 8)을 공유하게되므로 버스노선이 될 수 없다.
• 조건 3. 버스노선의 종점은 단말지점이어야 한다. 그리고 버스노선은 지점과 도로를 한 번씩만 지나야 한다. 예로 <그림 1>에서 2-7-8-3-1은 버스노선으로 가능하지만 2-7-9-7-8-10은 도로 (7, 9)와 지점 7을 두 번 방문하기 때문에 버스노선이 될 수 없다.
• 조건 4. 노선이 지나치게 길면 안되므로 위의 세 가지 조건을 만족하는 버스노선 중에서 가장 긴 노선의 길이가 최대한 짧게 설계되어야 한다. 단, 모든 도로의 길이는 1로 가정한다.

<그림 1>에서 제한조건을 만족하는 버스노선은 다음과 같다.

• 2-7-8-10
• 9-7-6
• 1-3-8-4-5

이 경우 가장 긴 노선의 길이가 4이다.

다음 <그림 2>와 같은 경우라면 위의 조건들을 만족시키는 버스노선은 존재하지 않는다. 왜냐하면 6-2-7-9가 버스노선이 되면 도로 (7, 8)은 다른 노선에 포함될 수 없고, 6번에서 시작하여 9번이 아닌 다른 곳이 종점이 된다면 9번의 다른 쪽 종점을 정할 수 없기 때문이다.

<그림 2>

트리도로망이 주어졌을 때, 위의 조건들을 만족하는 버스노선을 찾는 프로그램을 작성하시오.

입력

첫째 줄에는 도로망에 있는 지점 개수 n(2 ≤ n ≤ 500)이 주어진다. 둘째 줄부터 n-1개의 도로에 대한 정보가 한 줄에 하나씩 주어진다. 만일 지점 i와 지점 j 사이에 도로가 있다면 "i j"로 한 줄에 표시한다. 또는 "j i"라고 표시될 수도 있다. 숫자 사이에는 빈칸이 하나 있다. 지점은 1부터 n까지의 서로 다른 숫자로 표시된다.

출력

첫째 줄에는 제일 긴 노선의 길이를 출력한다. 둘째 줄에는 버스노선의 개수 m 을 출력한다. 다음 m 줄의 각 줄에는 위의 조건을 만족하는 버스노선 을 한 줄에 하나씩 출력한다. 한 버스노선은 노선에 포함된 지점의 개수와 한 종점 번호에서부터 다른 종점까지 거치는 지점 번호들을 차례로 출력한다. 지점 번호 사이에는 빈칸을 하나 둔다. 답이 여러 개인 경우는 그 중에 하나만 출력한다. 만일 위 네 가지 조건을 만족하는 답이 존재하진 않을 경우에는 첫째 줄에 숫자 0을 출력한다.

제한

힌트