시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 512 MB130322625.490%

문제

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

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

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

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

입력

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

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

출력

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

예제 입력 1

7
1 2
1 3
2 4
3 4
3 5
4 6
5 7

예제 출력 1

4 6

힌트

도시가 위와 같다면 도시의 불편함은 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)

출처

University > 경북대학교 > 2021 Goricon L번