← 返回题目列表

Codeforces · 2141/I

I. 给树上色

中文机器翻译题面 查看原题

给你一棵由 $$$n$$$ 个顶点组成的树。最初,树的所有顶点都没有着色。

您可以执行以下操作:选择任意两个顶点$$$u$$$和$$$v$$$(您可以选择$$$u=v$$$)并将它们之间的路径上的所有顶点(包括端点)用颜色$$$i$$$着色,其中$$$i$$$是您正在执行的操作的索引(即第一个操作使用颜色) $$$1$$$,第二个使用颜色 $$$2$$$,依此类推)。如果路径上的任何顶点之前已经着色,则其颜色将更改为新的颜色。

我们称树的着色为 完成 如果对于每个顶点,至少有一个操作已为其着色。

您的任务是计算两个值:

  • 实现完整着色所需的最少操作次数;
  • 用最少的操作次数可以获得不同的完整着色的数量(如果存在至少一个顶点$$$v$$$,使得第一个着色中$$$v$$$的颜色不同于第二个着色中$$$v$$$的颜色,则认为两个着色不同)。

输入

第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 32$$$) — 树中的顶点数。

接下来的 $$$(n-1)$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$) — 树的下一条边的端点。

对输入的附加约束:边定义具有 $$$n$$$ 顶点的有效树。

输出

打印两个整数——最少的操作次数以及用最少的操作次数可以获得的不同完整着色的数量。由于第二个数字可能非常大,因此输出它对 $$$998244353$$$ 取模。

示例

输入
复制

3
1 2
2 3

输出
复制

1 1

输入
复制

5
1 3
2 1
5 1
1 4

输出
复制

2 6

输入
复制

4
1 4
2 4
4 3

输出
复制

2 9

输入
复制

5
4 2
1 5
3 4
4 1

输出
复制

2 11

输入
复制

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

输出
复制

3 270