도로 점검

시간 제한1.5초메모리 제한512 MB

요약

그래프는 하나의 사이클과 그에 매달린 트리들로 이루어진 단일 사이클 그래프다. 검사할 수 있는 도로는 그래프를 연결 상태로 유지하는 간선, 즉 사이클 위의 간선뿐이다. 사이클 간선 하나를 제거하면 트리가 되고, 이때 불편함은 그 트리의 지름과 같다. N이 200,000까지 주어질 때 검사 가능한 도로의 수와, 사이클 간선을 하나 제거했을 때 얻을 수 있는 최대 지름을 구해야 한다.

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

문제

$1$ 번 도시부터 $N$ 번 도시까지 총 $N$ 개의 도시로 이루어진 나라가 있다. 도시들은 길이가 $1$ 인 양방향 도로 $N$ 개로 연결되어 있다. 임의의 두 도시는 하나 이상의 도로를 거쳐 항상 이동할 수 있으며, 두 도시 사이에 도로는 최대 하나만 존재한다.

정부는 시민들의 안전을 위해 주기적으로 도로를 점검한다. 도로를 점검하는 동안에는 그 도로로 이동할 수 없다. 어떤 도로를 점검했을 때 한 도시에서 다른 도시로 이동할 수 없게 되는 경우가 있는데, 이 경우 그 도로는 점검할 수 없다.

도로를 점검하면 최단 경로가 길어져서 불편해질 수 있다. 불편함은 모든 도시 쌍에 대한 최단 경로 중 가장 긴 경로의 길이로 정의된다.

정부를 위해 점검이 가능한 도로의 개수와, 하나의 도로를 점검할 때의 불편함 중 최댓값을 구하는 프로그램을 작성하자.

입력

첫 번째 줄에 도시의 개수와 도로의 개수를 나타내는 정수 $N$ ( $3 \leq N \leq 200,000$ )이 주어진다.

다음 $N$ 개의 줄에는 도로의 정보가 각 줄마다 $u,\ v\ (1 \leq u < v \leq N)$ 의 형태로 주어진다. 이는 $u$ 번 도시와 $v$ 번 도시를 잇는 도로가 존재한다는 의미이다.

출력

점검이 가능한 도로의 개수와 하나의 도로를 점검할 때의 불편함 중 최댓값을 공백을 사이에 두고 출력한다.

힌트

도시가 위와 같다면 도시의 불편함은 4이다. (5 - 4 - 3 - 6 - 7)

1번 도시와 2번 도시를 연결하는 도로를 점검하면 불편함은 그대로 4이다.

1번 도시와 3번 도시를 연결하는 도로를 점검하면 불편함은 5가 된다. (1 - 2 - 4 - 3 - 6 - 7)

2번 도시와 4번 도시를 연결하는 도로를 점검하면 불편함은 그대로 4이다.

3번 도시와 4번 도시를 연결하는 도로를 점검하면 불편함은 6이 된다. (5 - 4 - 2 - 1 - 3 - 6 - 7)

예제1

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