LHC

최신 극비 실험을 위해 다량의 힉스 보손이 필요하다. 이 붙잡기 힘든 입자를 얻으려면 거대 강입자 충돌기(large hadron collider), 즉 입자를 가속시켜 서로 충돌시키는 길고 둥근 터널을 지어야 한다.

이미 광범위한 터널망을 갖추고 있으며, 이 터널망은 연결되어 있고 순환 경로가 없음이 보장된다. 다시 말해 터널들은 트리(tree) 구조를 이룬다. 터널망은 $1$번부터 $N$번까지 번호가 붙은 $N$개의 분기점과, 두 분기점을 잇는 $N - 1$개의 터널로 이루어진다. 각 터널은 양방향으로 지날 수 있다.

두 분기점 사이에 터널을 정확히 하나 추가하면 순환 경로가 생기고, 이 순환이 충돌기가 된다. 충돌기의 길이는 그 순환에 포함된 터널의 개수로 정의한다. 가능한 한 가장 긴 충돌기를 만들고 싶으며, 동시에 그렇게 만들 수 있는 방법의 수, 즉 터널 하나를 추가했을 때 최대 길이의 순환이 만들어지는 서로 다른 분기점 쌍의 개수도 구하려 한다.

예를 들어 아래 터널망에서는 분기점 $1$과 $5$ 사이, 또는 $2$와 $5$ 사이에 터널을 놓아 길이 $4$짜리 충돌기를 만들 수 있다:

첫째 줄에 분기점의 개수 $N$ ($3 \le N \le 400\,000$)이 주어진다. 이어지는 $N - 1$개의 줄에는 각각 공백으로 구분된 두 정수 $i$와 $j$ ($1 \le i, j \le N$)가 주어지며, 이는 분기점 $i$와 $j$ 사이에 터널이 있음을 뜻한다. 터널들은 트리를 이룸이 보장된다.

한 줄에 공백으로 구분된 두 정수를 출력한다. 첫 번째는 만들 수 있는 가장 긴 충돌기의 길이(순환에 포함된 터널의 개수)이고, 두 번째는 그 최대 길이를 달성하는 서로 다른 분기점 쌍의 개수이다. 이 개수는 64비트 정수가 필요할 수 있다.