계통 트리

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

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

계통 트리에서 개체 사이의 가까운 정도만 뽑아내면 그래프 하나를 얻는다. 이 그래프를 계통 그래프라고 한다. 유사도가 $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$를 출력한다.