선로를 지켜라

아크마르와 이브마르가 전쟁 중이다. 당신은 전시의 아크마르 전역으로 보급품을 나르는 철도망을 책임지고 있다. 철도망은 여러 분기점에서 만나는 선로로 이루어진다. 한 분기점에서 만나는 선로 수에는 제한이 없지만, 두 분기점을 잇는 경로는 언제나 하나뿐이다. 어떤 분기점 사이에는 경로가 둘 이상 생기도록 선로를 더 놓자고 주장해 봤지만, 전시라 예산이 나오지 않았다.

그런데 이브마르에 심어 둔 이중간첩이 나쁜 소식을 가져왔다. 적의 첩보원이 한 달 안에 분기점 하나를 폭파할 계획이다. 어느 분기점인지는 모르지만, 적이 반드시 요충지를 노린다는 사실만은 확실하다. 요충지는 그 분기점을 없앴을 때 남은 분기점 쌍 가운데 경로가 사라지는 쌍이 가장 많아지는 분기점이다. 철도망을 다시 놓을 시간은 없으니, 지금 선로로 직접 이어져 있지 않은 두 분기점을 새 선로 하나로 잇는 것이 전부다. 적은 지금의 철도망을 보고 목표를 정했고, 새 선로를 놓아도 목표는 바뀌지 않는다.

경로가 사라지는 쌍의 수를 가장 적게 만드는 새 선로를 찾아라.

첫 줄에 철도망의 선로 수 $n$이 주어진다 ($2 \le n \le 10\,000$). 다음 $n$개의 줄에는 두 정수 $i_1$과 $i_2$가 주어지며, 분기점 $i_1$과 $i_2$가 선로로 이어져 있다는 뜻이다. 분기점 번호는 0부터 차례로 매겨지므로 철도망의 분기점은 모두 $n + 1$개이고 번호는 0번부터 $n$번까지이다. 모든 선로는 양방향이고, 같은 선로는 두 번 주어지지 않으며, 두 분기점을 잇는 경로는 정확히 하나뿐이다.

두 정수 $n_1$과 $n_2$를 공백으로 구분해 출력한다. $n_1$은 적이 요충지를 파괴했을 때 경로가 사라지는 분기점 쌍의 수이고, $n_2$는 새 선로를 가장 잘 놓았을 때에도 경로가 사라진 채로 남는 쌍의 수이다. 요충지는 항상 하나뿐이다.