[AGC024D] Isomorphism Freak

给定一棵点数为 $n$ 的无根树. 对于两个点 $u,v$, 若有以 $u$ 为根与以 $v$ 为根树同构, 则染上同一种颜色. 可以给这棵树加若干点, 问加完点后树最少能有多少种颜色, 以及在最少颜色的情况下最少有多少个叶子节点.

[problemUrl]: https://atcoder.jp/contests/agc024/tasks/agc024_d 木 $ 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 $ ビット符号付き整数に収まることが示せる。

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 $ を出力します。