题目描述

木 $G$ の頂点を何色かで塗り分ける方法が 良い彩色 であるとは、同じ色で塗られたどの $2$ つの頂点 $u,v$ に対しても、 $G$ を $u$ を根とする根付き木として見た木と $v$ を根とする根付き木として見た木が同型であることを指します。

また、$G$ の カラフルさ とは、$G$ の良い彩色で使われる色の種類数の最小値を指します。

$N$ 頂点の木が与えられます。頂点には $1$ から $N$ までの番号がついており、$i$ 本目の辺は頂点 $a_i$ と頂点 $b_i$ を結んでいます。 この木に以下の操作を何度か繰り返し施し、木 $T$ を作ります。

• 新たな頂点を $1$ つ作る。現在の木の頂点をひとつ選び、その頂点と新しく作った頂点を辺で結ぶ。

$T$ としてありうるもののカラフルさの最小値を求めてください。 さらに、その最小値を達成する木 $T$ の葉(次数 $1$ の頂点)の数の最小値を出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $a_1$ $b_1$ : $a_{N-1}$ $b_{N-1}$

输出格式

整数 $2$ つを空白区切りで出力せよ。 まずはじめに、作ることのできる木 $T$ の中での、カラフルさの最小値を出力せよ。 その後、その時の木の葉の数の最小値を出力せよ。

なお、この問題の制約の下で、出力すべき値は $64$ ビット符号付き整数に収まることが示せる。

题目大意

给定一棵点数为 $n$ 的无根树. 对于两个点 $u,v$, 若有以 $u$ 为根与以 $v$ 为根树同构, 则染上同一种颜色.

可以给这棵树加若干点, 问加完点后树最少能有多少种颜色, 以及在最少颜色的情况下最少有多少个叶子节点.

5
1 2
2 3
3 4
3 5

2 4

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

3 4

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

4 6

13
5 6
6 4
2 8
4 7
8 9
3 2
10 4
11 10
2 4
13 10
1 8
12 1

4 12

提示

ノート

$G$ を $u$ を根とする根付き木として見た木と $v$ を根とする根付き木として見た木が同型であるとは、 $G$ の頂点集合からそれ自身への全単射な写像 $f_{uv}$ であって、以下を満たすものが存在することを指します。

• $f_{uv}(u)=v$
• どの $2$ 頂点の組 $(a,b)$ についても、$(a,b)$ 辺があることと $(f_{uv}(a),f_{uv}(b))$ 辺があることが同値である

制約

• $2\ \leq\ N\ \leq\ 100$
• $1\ \leq\ a_i,b_i\ \leq\ N(1\leq\ i\leq\ N-1)$
• 与えられるグラフは木である

Sample Explanation 1

頂点 $6$ を用意し、頂点 $2$ と結んだとき、頂点 $(1,4,5,6)$ を赤で、頂点 $(2,3)$ を青で塗る彩色は良い彩色です。 $1$ 色で全頂点を塗る彩色は良い彩色ではないので、作った木のカラフルさは $2$ となることが分かります。 この場合が最適であり、葉は $4$ つあるので、$2$ と $4$ を出力します。