← 返回题目列表

AtCoder · utpc2021_d

D. 链图对

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

配点 : 100 点

問題文

具有以下性质的有向图 链图 。 所有满足

  • 不同的顶点 i, j, k , 当我输入 i \rightarrow j 和 按字典顺序比较 j \rightarrow k 的边时,也存在i \rightarrow k 的边。作为
  • 无向图来看,不存在自环或多重边。由

无向边组成 N 给定一个顶点的完全图。顶点编号为 1 减去 N 。开始时,N-1 条边被涂成红色,形成一棵树。第i 条红色边是连接 A_i 和 按字典顺序比较 B_i 的边。其余的边是白色的。

你将按顺序进行以下操作,确定图的边的颜色和方向。

  • 将所有白色的边分别涂成红色或蓝色。
  • 为所有红色的边和蓝色的边分别赋予方向。

仅由红色边和蓝色边组成的图 链图 作为经过操作后的可能存在的图的数量为 998244353 后求余数。

制約

  • 所有输入均为整数
  • 1 \le N \le 100
  • 1 \le A_i, B_i \le N
  • 给定的由红色边组成的图是树。

入力

输入是按以下格式从标准输入给出的。

N
A_1 B_1
\vdots
A_{N-1} B_{N-1}

出力

打印答案。 来自


入力例 1

3
1 2
2 3

出力例 1

10

以下两个图是可能的图的例子。

  


入力例 2

5
1 2
1 3
2 4
5 2

出力例 2

1304

可以考虑如下图。


入力例 3

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

出力例 3

793075136

答案 请打印除以 998244353 后的余数。