题目描述

有一棵包含 $N$ 个顶点的树，每个顶点编号为 $1,\ldots,N$。对于 $i=1,\ldots,N-1$，第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$。
对于这棵树的每个顶点，最多可以放置 $1$ 个棋子。我们定义如下操作：

• 将所有棋子同时移动到相邻的一个顶点上。

此外，满足以下条件的操作被称为良好操作：

• 对于每一条边，通过该边移动的棋子最多只有 $1$ 个。
• 操作后，每个顶点上最多只有 $1$ 个棋子。

高桥君决定选择至少 $1$ 个顶点，并在每个选中的顶点上各放置 $1$ 个棋子。棋子的放置方式共有 $2^N-1$ 种。请计算其中满足以下条件的放置方式的个数，并对 $998244353$ 取模：

• 对于所有非负整数 $K$，都满足以下条件：
  • 可以进行 $K$ 次良好操作。
  • 经过 $K$ 次良好操作后，棋子所在顶点的集合 $S_K$ 是唯一确定的。

输入格式

输入以如下格式从标准输入读入：

$N$
$a_1$ $b_1$
$\vdots$
$a_{N-1}$ $b_{N-1}$

输出格式

请输出答案。

样例 1

输入

3
1 2
1 3

输出

2

样例 2

输入

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

输出

0

样例 3

输入

19
9 14
2 13
1 3
17 19
13 18
12 19
4 5
2 10
4 9
8 11
3 15
6 8
8 10
6 19
9 13
11 15
7 17
16 17

输出

100

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq a_i < b_i \leq N$
• 给定的图是一棵树
• 所有输入均为整数

样例解释 1

有以下 $2$ 种满足条件的放置方式：

• 选择顶点 $1$ 和顶点 $2$，并放置棋子。
• 选择顶点 $1$ 和顶点 $3$，并放置棋子。
  请注意，必须选择至少 $1$ 个顶点。

样例解释 2

有时不存在满足条件的棋子放置方式。

由 ChatGPT 4.1 翻译