图：日本某动物园里一只头上顶着橙子的温泉水豚

在日本某处的动物园里，饲养员们决定和水豚玩以下游戏：

水豚的展区由 $N$ 个温泉组成，编号为 $0$ 到 $N - 1$。这些温泉由 $N - 1$ 条通道连接。每条通道连接两个温泉，并且可以通过这些通道从任意一个温泉到达其他任意一个温泉。换句话说，水豚展区具有树的结构（即无向连通无环图）。

最初，每个温泉中最多有一只水豚，但在游戏过程中这可能会发生变化。

游戏由若干轮（可能是无限轮）组成。每轮包含 2 个阶段：

1. 饲养员会将一个橙子扔进 $N$ 个温泉中的一个。水豚会知道橙子被扔进了哪个温泉。
2. 最多有一只水豚可以移动到相邻的温泉。之后，如果装有橙子的温泉中没有水豚，则饲养员获胜，水豚失败。否则，橙子被吃掉，游戏继续。

如果饲养员和水豚都采取最优策略，且饲养员无法在有限轮内赢得游戏，则称初始配置（即最初包含水豚的温泉集合）是安全的（safe）。

对于每个从 $0$ 到 $N$ 的 $K$，求出恰好含有 $K$ 只水豚的安全初始配置的数量。由于这些数量可能非常大，请输出它们模 $998244353$ 的余数。

实现细节

你需要实现以下函数：

std::vector<int> solve(int N, std::vector<int> U, std::vector<int> V)

该函数将被交互库（grader）调用一次，并应返回一个长度为 $N+1$ 的 std::vector<int>，其中包含对于每个 $0 \le K \le N$，恰好有 $K$ 只水豚的安全初始配置数量（模 $998244353$）。

该函数的参数具有以下含义：

• $N$ - 温泉的数量。
• $U$ - 一个长度为 $N - 1$ 的 std::vector<int>，包含 $N - 1$ 条通道中每条通道的第一个端点。
• $V$ - 一个长度为 $N - 1$ 的 std::vector<int>，包含 $N - 1$ 条通道中每条通道的第二个端点。

对于每个 $0 \le i < N - 1$，第 $i$ 条通道连接温泉 $U_i$ 和 $V_i$。

不要忘记包含头文件 "oranges.h"，否则会导致编译错误！

数据范围

• $1 \le N \le 6000$
• 对于每条通道 $(U_i, V_i)$，有 $0 \le U_i, V_i < N$ 且 $U_i \ne V_i$。
• 保证给定的通道构成一棵树（即无向连通无环图）。

样例

输入样例 1

1

输出样例 1

0 1

说明 1

唯一的安全初始配置是 $\{0\}$。

输入样例 2

4
0 1
1 2
2 3

输出样例 2

0 0 4 4 1

说明 2

第二个样例中水豚展区的结构：

有 4 个含有两只水豚的安全初始配置：$\{0, 2\}$，$\{0, 3\}$，$\{1, 2\}$，$\{1, 3\}$。

所有含有至少 3 只水豚的初始配置都是安全的。

输入样例 3

6
0 1
1 2
1 3
0 4
4 5

输出样例 3

0 0 0 0 11 6 1

说明 3

第三个样例中水豚展区的结构：

例如，初始配置 $\{1, 3, 4\}$ 是不安全的：

在第一轮中，饲养员会将橙子扔进温泉 5。温泉 4 中的水豚被迫移动到温泉 5。

在第二轮中，饲养员会将橙子扔进温泉 2。温泉 1 中的水豚被迫移动到温泉 2。

在第三轮中，饲养员会将橙子扔进温泉 0。由于没有水豚可以移动到温泉 0，饲养员获胜。

输入样例 4

15
0 1
0 2
2 3
3 4
4 5
5 6
0 7
7 8
8 9
9 10
8 11
11 12
7 13
7 14

输出样例 4

0 0 0 0 0 0 0 0 0 560 992 793 361 98 15 1

说明 4

第四个样例中水豚展区的结构：