시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 256 MB5411927.273%

문제

1번 도시부터 N번 도시까지 총 N개의 도시가 있는 나라가 있습니다. 도시들은 길이가 1인 도로로 연결될 수 있고 이런 양방향 도로도 N개가 있습니다. 

임의의 두 도시는 여러 개의 도로를 통하여 항상 이동할 수 있도록 설계되었습니다. 또한 도로는 두 도시 사이에 최대 하나만 존재합니다.

불편함은 모든 도시 쌍에 대하여 최단 경로가 가장 긴 경로의 길이로 정의됩니다.

정부는 시민들의 안전을 위하여 주기적으로 도로를 점검합니다. 도로를 점검하면 해당 도로를 이용할 수 없습니다. 

어떤 도로를 점검하면 한 도시에서 다른 도시로 이동할 수 없을지도 모릅니다. 이럴 때는 해당 도로를 점검할 수 없습니다. 

정부는 점검이 가능한 도로의 개수와 하나의 도로를 점검했을 때 불편함의 최댓값을 알고 싶습니다.

입력

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

다음 N개의 줄에는 도로의 정보가 주어집니다. 각 줄 마다 u, v (1 ≤ u < v ≤ 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번