다음 일급 비밀 실험을 위해 많은 양의 힉스 입자가 필요해졌습니다. 이 잡기 어려운 입자를 모으기 위해 대형 강입자 충돌기 (LHC)가 필요해졌습니다. LHC는 원 모양의 큰 터널로 입자를 가속시킬 수 있는 공간입니다.

나는 이미 만들어져있는 터널을 사용할 권한이 있습니다. 이 터널은 트리 모양으로 사이클이 존재하지 않습니다. 이 터널 네트워크는 1부터 N까지 번호지어진 N개의 교차점과 두 교차점을 잇는 N-1개의 터널로 이루어져있습니다. 이 터널은 양방향으로 오고 갈 수 있습니다. (예를들어 교차점 a에서 b로 갈 수 있다면 b에서 a로도 갈 수 있습니다.)

이 터널 네트워크에 딱 하나의 터널을 더 뚫는다면 우리는 사이클을 만들 수 있습니다. 이 사이클이 바로 내가 필요한 LHC가 될 것입니다. 나는 가능한한 가장 긴 사이클을 만들려고 합니다. 가장 긴 사이클은 가장 많은 터널을 지나가는 사이클로 정의하겠습니다. 그리고 다른 경로를 통하는 가장 긴 사이클이 총 몇 개인지도 알고싶어 합니다.

예를들어 다음과 같은 터널 네트워크가 있을 때, 1번과 5번 혹은 2번과 5번 교차점을 연결해 길이 4의 터널을 만들 수 있습니다.

입력

• 첫번째 줄에 교차점의 갯수, N (3 ≤ N ≤ 400000)이 입력됩니다.
• 다음 N-1 줄에 두 교차점 i, j를 잇는 터널 정보가 공백으로 구분되어 입력됩니다. (1 ≤ i,j ≤ N)

출력

• 첫 번째 정수는 가장 긴 사이클의 길이,
• 두 번째 정수는 사이클을 만들 수 있는 가짓수입니다.

입출력 예

입력

5
1 3
2 3
3 4
4 5

출력

4 2

출처:CEMC (CCC 2013 Stage 2)
번역:ladown21