大样例在题库第3587题下载

树 (tree)

题目描述

给出一棵有 $N$ 个点的树，编号 $1 \sim N$，第 $i$ 条边连接点 $A_i$ 和 $B_i$。 初始时有一个空序列，树上 $N$ 个点均为白色。

现在按边的编号从小到大考虑每一条边： 如果这条边连接的两个点都为白色，则选择其中一个点涂成黑色，将该点编号放入序列末端。否则不进行操作。

求完成上述操作后可能得到的不同的序列数量，答案对 $998244353$ 取模。

输入格式

在文件 tree.in 中读入。

第一行一个正整数 $N$ 表示树的点数； 接下来 $N-1$ 行每行两个正整数 $A_i,B_i$，代表第 $i$ 条边连接的两个点。

输出格式

在文件 tree.out 中输出。

一行一个整数，表示合法不同序列数量模 $998244353$ 的结果。

样例

样例输入 #1

5
1 2
1 3
1 4
1 5

样例输出 #1

5

样例输入 #2

7
7 2
7 6
1 2
7 5
4 7
3 5

样例输出 #2

10

数据范围

• $2 \le N \le 10^6$
• $1 \le A_i,B_i \le N$