계통 트리

시간 제한1초메모리 제한128 MB

요약

두 유기체의 계통수 거리가 3 이하일 때 연결된 그래프가 주어질 때, 이 그래프를 만드는 계통수 중 간선 수가 가장 적은 것의 간선 수를 구한다.

난이도: 어려움10점 중 9점
유형: 그래프, 트리, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

생물 개체 사이의 계통 관계를 밝히는 일은 생물정보학의 기본 과제다. 계통 관계는 보통 트리로 나타내고, 이 트리를 계통 트리라고 한다.

계통 트리에서 각 개체는 잎 노드 하나에 대응한다. 개체에 대응하지 않는 노드는 내부 노드라고 하며, 개체끼리 에지로 바로 이어지는 일은 없다. 두 잎 노드를 잇는 경로의 길이는 그 두 개체가 진화생물학적으로 얼마나 가까운지를 나타낸다.

계통 트리에서 개체 사이의 가까운 정도만 뽑아내면 그래프 하나를 얻는다. 이 그래프를 계통 그래프라고 한다. 유사도가 $K$ 인 계통 그래프는 다음과 같이 정의한다. 정점은 각 개체이고, 두 정점을 잇는 에지가 있을 필요충분조건은 계통 트리에서 두 정점에 대응하는 잎 노드 사이의 거리, 즉 경로의 길이가 $K$ 이하인 것이다.

실험실에서 유사도 3인 계통 그래프를 만든 뒤 계통 트리 자료를 잃어버렸다. 남은 그래프만 보고 트리를 복원하려는데, 같은 계통 그래프를 정의하는 계통 트리가 여러 개일 수 있다. 그래서 그중 가장 작은 트리, 즉 에지가 가장 적은 트리의 크기를 구하려고 한다.

유사도 3인 계통 그래프가 주어질 때, 이 그래프를 정의하는 계통 트리 가운데 에지 개수가 가장 적은 것의 에지 개수를 구하는 프로그램을 작성하시오. 입력으로 주어지는 계통 그래프는 항상 연결 그래프이고, 이 그래프를 정의하는 계통 트리가 반드시 존재한다.

입력

첫째 줄에 계통 그래프의 정점 개수 $N$ ( $2 \le N \le 5000$ )이 주어진다. 정점은 1번부터 $N$ 번까지 번호로 구분한다.

둘째 줄에 계통 그래프의 에지 개수 $M$ ( $1 \le M \le 10^6$ )이 주어진다.

다음 $M$ 개 줄에는 각 줄마다 에지 하나의 양 끝 정점 번호 $v$ , $w$ ( $1 \le v, w \le N$ )가 주어진다.

출력

첫째 줄에 주어진 계통 그래프를 정의하는 계통 트리 가운데 에지 개수가 가장 적은 것의 에지 개수 $S$ 를 출력한다.

예제3

예제 1
입력
```
6
7
1 2
2 3
3 1
3 4
3 5
5 6
6 3
```
예상 출력
```
9
```
예제 2
입력
```
3
3
1 2
1 3
2 3
```
예상 출력
```
3
```
예제 3
입력
```
3
2
1 2
2 3
```
예상 출력
```
5
```