给你一棵拥有 $n$ 个节点的树。每条边的长度均为 $1$。对于任意非空节点集合 $S$，$value(S)$ 定义为所有点对 $(u, v) \in S$ 之间距离 $dis(u, v)$ 的最大值，其中 $dis(u, v)$ 表示树上 $u$ 和 $v$ 之间的距离。

易知 $value(S)$ 满足 $0 \le value(S) < n$。对于每个 $0 \le K \le n - 1$，输出满足 $value(S) = K$ 的子集 $S$ 的数量。

输入格式

输入的第一行包含一个整数 $n$（$1 \le n \le 3000$），表示图中的节点数。

接下来 $n - 1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$），表示 $u$ 和 $v$ 之间存在一条边。

保证给定的图是一棵树。

输出格式

输出一行，包含恰好 $n$ 个整数。第 $i$ 个整数必须是满足 $value(S) = i - 1$ 的非空子集 $S$ 的数量。由于答案可能非常大，请将每个答案对 $998\,244\,353$ 取模后输出。

样例

输入样例 1

2
1 2

输出样例 1

2 1

输入样例 2

4
1 3
2 4
4 1

输出样例 2

4 3 4 4