← 返回题目列表

Codeforces · 1172/B

B. Nauuo 和 Circle

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

Nauuo是一个喜欢画圆圈的女孩。

有一天,她画了一个圆圈,想在上面画一棵树。

树是一个无向连通图,由 $$$n$$$ 节点和 $$$n-1$$$ 边组成。节点编号从 $$$1$$$ 到 $$$n$$$。

Nauuo 想要在圆上画一棵树,树的节点应该在圆上 $$$n$$$ 不同的点上,并且边缘应该是直的而不互相交叉。

“不相交”是指每两条边没有公共点或者唯一的公共点是两条边的端点。

Nauuo 想要使用 $$$n$$$ 元素的排列来绘制树。 $$$n$$$ 元素的排列是整数 $$$p_1,p_2,\ldots,p_n$$$ 的序列,其中从 $$$1$$$ 到 $$$n$$$ 的每个整数只出现一次。

选择排列后,Nauuo 在圆上第 $$$p_i$$$ 个点中绘制第 $$$i$$$ 个节点,然后绘制连接节点的边。

树给定了,Nauuo想知道有多少种排列才能使得画出的树满足规则(边是直的而不互相交叉)。她只想知道答案模$$$998244353$$$,你能帮助她吗?

显然,排列是否有效并不取决于选择圆上的哪些 $$$n$$$ 点。

输入

第一行包含一个整数 $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — 树中的节点数。

接下来的 $$$n-1$$$ 行中的每一行都包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1\le u,v\le n$$$),表示 $$$u$$$ 和 $$$v$$$ 之间有一条边。

保证给定的边形成一棵树。

输出

输出包含一个整数 - 适合在满足规则的圆上绘制给定树的排列数,以 $$$998244353$$$ 为模。

示例

输入 #1

4
1 2
1 3
2 4

输出 #1

16

输入 #2

4
1 2
1 3
1 4

输出 #2

24

注意

示例 1

所有有效排列及其生成树如下。

这是无效排列的示例:边 $$$(1,3)$$$ 和 $$$(2,4)$$$ 交叉。

示例 2

每个排列都会产生一棵有效的树,所以答案是 $$$4! = 24$$$。