分数: 1500 点
问题陈述
你得到一棵树 T 与 N 顶点编号 1 to N。 的 i第一条边连接顶点 A_i 和 B_i.
您可以执行以下操作任意次数,可能为零。
- 选择两片叶子 u 和 v of T 使它们之间的距离为奇数。然后,移除 u 和 v 来自 T (连同相关的边)。
在这里,当某个顶点在操作时的度正好为一时,该顶点被称为叶子。 两个顶点之间的距离是连接这两个顶点的路径中的边数。
求模数 998244353,可以作为顶点集的集合 T 操作后。
约束
- 2 \leq N \leq 150
- 1 \leq A_i,B_i \leq N
- 输入图是一棵树。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}
输出
打印答案。
示例输入 1
4 1 2 2 3 3 4
示例输出 1
3
执行零次操作会得到顶点集 \{1,2,3,4\}.
删除叶子 1 和 4 来自 T 会得到顶点集 \{2,3\}.
从这个状态开始,删除叶子 2 和 3 会得到顶点集 \{\}.
示例输入 2
5 2 1 3 1 4 1 5 3
示例输出 2
3
示例输入 3
8 2 1 3 2 4 1 5 2 6 5 7 3 8 7
示例输出 3
11
示例输入 4
24 12 7 14 4 8 13 24 13 1 3 4 9 17 2 1 21 24 22 11 1 15 17 22 5 23 10 24 12 13 6 12 16 10 21 19 22 20 17 4 20 20 6 10 18 21 6
示例输出 4
5359