문제3)

<그림 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번의 다른 쪽 종점을 정할 수 없기 때문이다.

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