题目描述

将树 $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$ 位有符号整数的范围。

样例 1

输入

5
1 2
2 3
3 4
3 5

输出

2 4

样例 2

输入

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

输出

3 4

样例 3

输入

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

输出

4 6

样例 4

输入

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

说明/提示

说明

以 $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 翻译