버스 노선 |
---|
문제3) <그림 1>은 어떤 도시의 도로망을 나타내고 있다. 이 도시의 지점은 숫자를 포함하는 동그라미로 표시되어 있고, 두 지점 사이에 있는 도로는 두 지점 을 잇는 선으로 표시되어 있다. 이 도로망의 특성은 다음과 같다. •특성 1. 임의의 한 지점에서 도로와 지점을 거쳐 모든 다른 지점으로 갈 수 있다. 위의 세 가지 특성을 만족하는 도로망을 트리도로망이라 한다. 이제 이 도시에서 몇 개의 버스노선을 신설하려고 한다. 각각의 버스노선은 한 종점에서 반대편 종점까지 가는 도로와 지점으로 이루어진다. 종점이 될 수 있는 지점은 도로망에서 단말지점(자신과 연결된 다른 지점이 하나 뿐인 곳)이어야 한다. 예를 들어, <그림 1>에서 버스 종점이 될 수 있는 지점은 색칠된 1, 2, 5, 6, 9, 10번 지점이다. <그림 1>과 같은 경우에 두 개씩의 단말지점으로 짝을 지어 세 개의 서로 다른 버스노선을 만들 수 있다. 단, 버스 노선을 설정하기 위해서는 다음 조건들을 만족해야 한다. •조건 1. 도시의 모든 지점은 반드시 하나의 노선에 포함되어야 하고, 두 개 이상의 버스 노선에 포함 될 수도 있다. 예를 들어, 1-3-8-10 노선과 9-7-8-4-5 노선과 같이 한 교차지점을 공유하 는 것은 허용된다. <그림 1>에서 제한조건을 만족하는 버스노선은 다음과 같다. 2-7-8-10 이 경우 가장 긴 노선의 길이가 4이다. 다음 <그림 2>와 같은 경우라면 위의 조건들을 만족시키는 버스노선은 존재하지 않는다. 왜냐하면 6-2-7-9가 버스노선이 되면 도로 (7, 8)은 다른 노선에 포함될 수 없고, 6번에서 시작하여 9번이 아닌 다른 곳이 종점이 된다면 9번의 다른 쪽 종점을 정할 수 없기 때문이다. 트리도로망이 주어졌을 때, 위의 조건들을 만족하는 버스노선을 찾는 프로그램을 작성하시오. |
입력 | |
---|---|
첫째 줄에는 도로망에 있는 지점 개수 n(2≤n≤500)이 주어진다. 둘째 줄부터 n-1 개의 도로에 대한 정보가 한 줄에 하나씩 주어진다. 만일 지점 i 와 지점 j 사이에 도로가 있다면 "i j"로 한 줄에 표시한다. 또는 "j i"라고 표시될 수도 있다. 숫자 사이에는 빈칸이 하나 있다. 지점은 1부터 n 까지의 서로 다른 숫자로 표시된다. |
출력 | |
---|---|
첫째 줄에는 도로망에 있는 지점 개수 n(2≤n≤500)이 주어진다. 둘째 줄부터 n-1 개의 도로에 대한 정보가 한 줄에 하나씩 주어진다. 만일 지점 i 와 지점 j 사이에 도로가 있다면 "i j"로 한 줄에 표시한다. 또는 "j i"라고 표시될 수도 있다. 숫자 사이에는 빈칸이 하나 있다. 지점은 1부터 n 까지의 서로 다른 숫자로 표시된다. |
예시 | |||
---|---|---|---|
1 | 입력 | 10 1 3 3 8 8 4 4 5 8 10 7 8 6 7 2 7 9 7 | |
출력 | 4 3 2 7 8 10 9 7 6 1 3 8 4 5 |