Dona Minhoca

Dona Minhoca construiu uma bela casa, composta de N salas conectadas por N-1 túneis. Cada túnel conecta exatamente duas salas distintas, e pode ser percorrido em qualquer direção. A casa de dona Minhoca foi construída de modo que, percorrendo os túneis, é possível partir de qualquer sala e chegar a qualquer outra sala da casa.

Dona Minhoca quer se exercitar, e para isso planeja construir um túnel adicional, de modo a criar um "ciclo" de salas e túneis. Vamos chamar de comprimento do ciclo o número de salas do ciclo.

A figura (a) abaixo mostra um exemplo de casa. É possível obter um ciclo de comprimento três construindo um túnel entre as salas 2 e 5, ou um ciclo de comprimento quatro construindo um túnel entre as salas 1 e 3.

Dada a descrição da casa de dona Minhoca, escreva um programa para determinar o número de salas do ciclo de maior comprimento que é possível construir, e de quantas maneiras é possível construir um ciclo com esse comprimento.

Entrada

A primeira linha da entrada contém um inteiro N, o número de salas da casa de dona Minhoca. As salas são identificadas por números de 1 a N. Cada uma das N-1 linhas seguintes contém dois inteiros X e Y, indicando que há um túnel entre a sala X e a sala Y.

Saída

Seu programa deve produzir duas linhas. A primeira linha deve conter somente um inteiro, o número de salas do ciclo de maior comprimento que é possível construir. A segunda linha deve conter somente um inteiro, o número de ciclos distintos que é possível contruir com esse comprimento.

Restrições

• 3 ≤ N ≤ 50 000
• 1 ≤ X ≤ N; 1 ≤ Y ≤ N; X ≠ Y
• nos testes, o número de possíveis ciclos distintos é menor do que 100 000 000

Informações sobre a pontuação

• Para um conjunto de casos de testes valendo 40 pontos, N ≤ 5 000
• Para um conjunto de casos de testes valendo outros 60 pontos, nenhuma restrição adicional.

Exemplos

5
1 2
2 4
4 5
4 3

4
2
	

8
1 2
2 3
3 4
3 6
5 3
1 8
1 7

5
6