树的重心

题目描述

一颗具有 $𝑛$ 个点的无根树，若以某个结点为整棵树的根，它子节点的最大子树(小于等于 $\frac {n}{2}$ )最小，则称这个点为树的重心。

给定一棵树,求树的重心的编号以及重心删除后得到的最大子树的节点个数size,如果size相同就选取编号最小的.

输入

第一行，$n$, 表示此无根树的结点数，接下来的 $n-1$ 行，每行两个数 $u, v$，表示两结点之间有边连接。 $2\leq n\leq 10^5$ .

输出

两行， 第一行一个数表示树的重心编号，第二行表示其中最大子树的节点个数。

样例

3
1 2
1 3

1 1

Limitation

1s, 1024KiB for each test case.