편극

언젠가 이런 날이 오리라는 것은 모두가 알고 있었다. 위험도 몇 해를 함께 살다 보면 그저 일상이 되고, 그러다 무게를 잃는다.

오늘 비토티아의 통치자 비타드가 비테오티아의 왕 비테아사르에게 보낸 서한이 공개되었다. 비토티아는 비테오티아 전체를 병합하라고 요구했고, 따르지 않으면 비트 편극 자석(BPM)을 쓰겠다고 했다.

BPM이 작동하면 비테오티아의 모든 도로가 일방통행으로 바뀐다. 비테오티아는 도로망을 최소한으로만 깔아 두어서 어느 두 도시 사이에도 오가는 길이 정확히 하나뿐이다. 그래서 이 한 방은 치명적일 수 있다.

BPM이 도로망을 얼마나 망가뜨릴 수 있는지 구하라. 모든 도로의 방향이 정해진 뒤에도 그 방향을 지키며 한쪽 도시에서 다른 쪽 도시로 갈 수 있는 도시 쌍의 개수를 센다. 도로의 방향을 정하는 모든 방법을 통틀어 이 개수의 최솟값과 최댓값을 구하라.

첫째 줄에 비테오티아의 도시 수를 나타내는 정수 $n$ ($1 \le n \le 250\,000$)이 주어진다. 도시에는 $1$번부터 $n$번까지 번호가 붙어 있다.

다음 $n-1$개 줄에는 각각 정수 $u$와 $v$ ($1 \le u \le v \le n$)가 주어진다. 도시 $u$와 도시 $v$를 직접 잇는 도로가 있다는 뜻이고, 이 도로는 아직 양방향이다. 도로망은 어느 두 도시 사이에도 오가는 길이 정확히 하나만 있는 형태로 이어져 있다.

한 줄에 정수 두 개를 공백으로 구분해 출력한다. 편극이 끝난 뒤에도 한 방향으로 오갈 수 있는 도시 쌍 개수의 최솟값을 먼저, 최댓값을 그다음에 출력한다.