题目内容

塔子哥是一个聪明勇敢的探险家。他听说有一棵神秘的树，据说在它的某个节点上藏有一个宝藏。为了寻找这个宝藏，塔子哥决定前往这棵树所在的深山探险。

经过漫长的征途，塔子哥终于到达了这棵树的附近。他仔细观察这棵树，发现它非常美丽，树干粗壮，树叶繁茂，枝干交错。但是，他也发现了一个问题：这棵树的某个节点上藏有宝藏，但是这个节点与其他节点之间的连接关系非常复杂，很难直接找到宝藏。

经过一番思考之后，塔子哥决定采用一种特殊的方法来寻找宝藏。他发现，如果他能够找到树上的某一条边，并删除它，那么这棵树就会被分成两个部分 $A$ 和 $B$，而宝藏可能就在其中的某一部分中。

但是，塔子哥也知道，他不能随便删除一条边，因为他需要保证两个部分的节点数的差的绝对值 $||A|-|B||$ 尽可能小，才能有更大的机会找到宝藏。因此，他需要找到最优的划分方案。

现在，他想请你输出最小的 $||A|-|B||$ 和最优方案的数量，使得他有更大的机会找到宝藏。

输入描述

第一行一个整数 $n$ 表示节点的数量，节点从 $1$ 到 $n$ 编号。

接下来 $n-1$ 行每行两个正整数 $s$ ， $t$ ，表示 $s$ 的父亲是 $t$ 。

输入保证是一棵树。

对于所有数据 $1\le n\le 100000$ 。

输出描述

输出一行两个整数，用空格分开，分别表示最优解和最优方案数。

样例

输入

3
2 1
3 1

输出

1 2