给你一个有根树,由 $$$n$$$ 顶点组成,编号从 $$$1$$$ 到 $$$n$$$。树的根是顶点$$$1$$$。
您必须将树的所有顶点着色为 $$$n$$$ 颜色(也编号从 $$$1$$$ 到 $$$n$$$),以便每种颜色恰好有一个顶点。设 $$$c_i$$$ 为顶点 $$$i$$$ 的颜色,$$$p_i$$$ 为有根树中顶点 $$$i$$$ 的父节点。如果没有顶点 $$$k$$$ ($$$k > 1$$$) 使得 $$$c_k = c_{p_k} - 1$$$,则着色被认为是漂亮的,i。 e.没有顶点的颜色比其父级的颜色精确 $$$1$$$。
计算美丽颜色的数量,并以 $$$998244353$$$ 为模打印。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 250000$$$) — 树中的顶点数。
接下来是 $$$n-1$$$ 行,第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$) 表示顶点 $$$x_i$$$ 和顶点$$$y_i$$$。这些边形成一棵树。
输出
打印一个整数 — 漂亮颜色的数量,以 $$$998244353$$$ 为模。
示例
输入 #1
5 1 2 3 2 4 2 2 5
输出 #1
42
输入 #2
5 1 2 2 3 3 4 4 5
输出 #2
53
输入 #3
20 20 19 20 4 12 4 5 8 1 2 20 7 3 10 7 18 11 8 9 10 17 10 1 15 11 16 14 11 18 10 10 1 14 2 13 17 20 6
输出 #3
955085064