DFS 序

题目描述

小 A 有一棵以顶点 1 为根的树，这棵树有 $n$ 个节点。这 $n$ 个节点编号从 1 到 $n$。

现在，小 A 想要从根节点开始进行深度优先搜索（DFS）。他想知道对于每个节点 $v$，它在深度优先搜索顺序的第 $j$ 个位置出现的方式有多少种。节点在第 $j$ 个位置（$1 \leq j \leq n$）出现意味着在访问该节点之前已经访问了 $j − 1$ 个其他节点。由于一个节点的子节点可以以任意顺序遍历，因此可能存在多种深度优先搜索的顺序。

小 A 想知道对于每个节点 $v$ 和每个位置 $j$ （$1 \leq v, j \leq n$），有多少不同的深度优先搜索顺序使得 $v$ 出现在第 $j$ 个位置。由于答案可能非常大，请输出结果对 $998244353$ 取模。

以下是深度优先搜索的伪代码。在调用 main() 函数后，dfs_order 将是深度优先搜索的顺序。

输入格式

小 A 正在处理一棵树。输入的第一行包含一个整数 $n$ ($1 \leq n \leq 500$)，表示树中顶点的数量。

接下来的 $n − 1$ 行描述了树的边。第 $i$ 条边由两个整数 $u_i$ 和 $v_i$ 表示，它们是连接的顶点标签（$1 \leq u_i, v_i \leq n, u_i \neq v_i$）。可以保证给定的边形成一棵树。

输出格式

输出时，对于每个顶点 $v$（从 1 到 $n$），输出一行包含 $n$ 个整数的结果，结果对 $998244353$ 取模。第 $v$ 行中的第 $j$ 个整数应该表示不同的深度优先搜索顺序，使得 $v$ 出现在第 $j$ 个位置。输出一个非负整数，表示答案对 $998244353$ 取模之后的结果。

样例 #1

样例输入 #1

5
1 2
1 3
3 4
3 5

样例输出 #1

4 0 0 0 0
0 2 0 0 2
0 2 2 0 0
0 0 1 2 1
0 0 1 2 1

提示

数据范围