You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

给出一棵有n+1个结点的树，结点编号0~n.

1. 问删除一个结点后，不连通的结点对最多有多少对？ (i,j)与(j,i)视为同一个结点对。
2. 在1的基础上，删除一个节点后，给这个图添加一条边，使得恢复连通的结点对最多(不连通的最少)。问此时不连通的结点对有多少对？

Format

Input

第一行n， 接下来n行，代表n条边。

Output

两个整数，分别为2个问题的答案。

Samples

6
0 1
1 2
2 3
2 4
4 5
4 6

11 5

提示

删除点2，不连通的有11对。1与4连边，不连通的有5对。

Limitation

$2 \le n \le 10000$