레이팅 미적용생물 개체들 사이에 대한 계통 관계를 구성하는 것은 생물정보학에서 매우 중요한 작업이다. 계통 관계는 보통 트리로 표현되는데, 이를 계통 트리라고 부른다. 각 개체는 계통 트리에서 잎 노드(leaf node)에 대응된다. 계통 트리에서 두 잎 노드 사이의 경로 길이는 해당 노드에 대응되는 두 개체가 진화생물학적으로 가까운 정도를 나타낸다. 아래 그림은 계통 트리의 예를 보여준다.
계통 트리를 참고하여 개체들 사이에서 진화생물학적으로 가까운 정도를 나타내는 그래프를 정의할 수 있다. 이 그래프를 계통 그래프라고 부른다. 유사도 K인 계통 그래프는 다음과 같이 정의된다. 그래프의 정점은 각 개체를 나타내고, 두 정점 사이에 에지가 존재할 필요충분조건은 계통 트리에서 이 두 정점에 대응되는 노드들 사이의 거리(경로의 길이)가 K 이하인 경우이다. 아래 그림은 위 계통 트리에 의해 정의되는 유사도 \(K=3\)인 그래프를 보여준다.
실험실에서 유사도 3인 계통 그래프를 구축한 후에 계통 트리에 대한 자료를 분실하였다. 따라서 계통 트리를 복원하기 위한 작업을 수행하려고 한다.
유사도 3인 계통 그래프가 주어질 때, 이 그래프를 정의해 주는 계통 트리를 구하는 프로그램을 작성하시오. 입력으로 주어지는 계통 그래프는 항상 연결 그래프이며 이 그래프에 대한 계통 트리가 반드시 존재한다는 것에 유의하시오.
※ 이 문제의 채점 데이터는 공개된 공식 데이터가 없어 재구성한 것입니다. 문제 지문은 원본(정보올림피아드 기출)을 따릅니다.
첫째 줄에는 계통 그래프의 정점의 개수를 나타내는 정수 \(N(2 \le N \le 5{,}000)\)이 주어진다. 정점들은 1부터 N까지의 번호로 구분된다. 둘째 줄에는 계통 그래프 에지의 개수를 나타내는 정수 \(M(1 \le M \le 1{,}000{,}000)\)이 주어진다. 그 다음 M개의 줄에는 각 줄마다 계통 그래프의 한 에지의 양끝 정점 번호를 나타내는 두 개의 정수 v, \(w(1 \le v,\) \(w \le N)\)가 주어진다.
첫째 줄에 계통 트리의 에지의 개수 S를 출력한다. 그 다음 S개의 줄에는 각 줄마다 각 에지의 양끝 정점 번호인 v, w를 빈칸 한 개를 사이에 두고 출력한다. 트리 에지들은 임의의 순서로 출력하면 된다. 단, 트리 노드의 번호를 1부터 N까지는 잎 노드들을 위해서 배정해야 한다. 또한, 입력으로 주어진 계통 그래프의 정점과 이에 대응되는 계통 트리의 잎 노드는 서로 같은 번호를 사용해야 한다. 나머지 내부 노드의 번호는 N+1부터 S+1까지 임의로 정할 수 있다. 계통 트리가 하나 이상 존재하는 경우, 그 중에 하나만 구해 출력한다.
6
7
1 2
2 3
3 1
3 4
3 5
5 6
6 3
9
1 7
2 7
3 8
4 9
5 10
6 10
7 8
8 9
8 10
생성자가 기록되지 않았습니다.
출처 올림피아드 > 한국정보올림피아드 > KOI 2008 > 2차 대회 > 고등부 2번