AT_agc024_d.[AGC024D] Isomorphism Freak

将树 $G$ 的顶点用若干种颜色进行染色，如果对于任意两个被染成同一种颜色的顶点 $u,v$，以 $u$ 为根的有根树和以 $v$ 为根的有根树同构，则称这种染色方式为良好染色。

树 $G$ 的多彩度定义为 $G$ 的所有良好染色中所使用颜色种类数的最小值。

给定一棵有 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$，第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$。你可以多次进行如下操作，构造出一棵新的树 $T$：

• 新建一个顶点，从当前树中选择一个顶点，将新顶点与其通过一条边连接。

请你求出所有可能构造出的树 $T$ 中，多彩度的最小值。并且，在达到该最小多彩度的情况下，输出此时树 $T$ 的叶子（度数为 $1$ 的顶点）数的最小值。

输入以如下格式从标准输入读入：

$N$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_{N-1}$ $b_{N-1}$

请输出两个整数，用空格隔开。首先输出所有可能构造出的树 $T$ 中的最小多彩度，然后输出在达到该最小多彩度时树 $T$ 的最小叶子数。

在本题的约束下，输出的值保证不会超过 $64$ 位有符号整数的范围。

说明

以 $u$ 为根的有根树和以 $v$ 为根的有根树同构，指的是存在 $G$ 的顶点集合到自身的一个双射 $f_{uv}$，满足：

• $f_{uv}(u) = v$
• 对于任意两个顶点对 $(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)$
• 给定的图保证是一棵树

样例说明 1

如果新建顶点 $6$ 并与顶点 $2$ 相连，将顶点 $(1,4,5,6)$ 染成红色，顶点 $(2,3)$ 染成蓝色，这是一种良好染色。用 $1$ 种颜色染所有顶点不是良好染色，因此该树的多彩度为 $2$。这种情况下叶子数为 $4$，所以输出 $2\ 4$。

由 ChatGPT 4.1 翻译