#P17881. Domain Compression

Domain Compression

Gojo 有一棵包含 nn 个顶点的树,顶点编号为 1,2,…,n1,2,\ldots,n。他可以进行如下操作:

  1. 选择一个尚未被删除的顶点 vv。
  2. 对于当前图中与 vv 相邻的每一对不同顶点 u,wu,w,如果 u,wu,w 之间还没有边,就添加一条连接它们的无向边。
  3. 删除顶点 vv 以及所有与它相连的边。

对每个 k=1,2,…,nk=1,2,\ldots,n,考虑所有恰好进行 kk 次操作的方式。每种方式由依次选择的 kk 个不同顶点确定,因此一共有 n!(n−k)!\dfrac{n!}{(n-k)!} 种方式。

对于每个 kk,求所有这些方式执行结束后,剩余图的边数之和,并对 998244353998244353 取模。

注意:不同的顶点删除顺序计为不同的方式,即使它们得到相同的最终图。

输入格式

第一行一个整数 nn。

接下来 n−1n-1 行,每行两个整数 ui,viu_i,v_i,表示原树的一条边。

输出格式

输出 nn 个整数,第 kk 个整数是恰好进行 kk 次操作时所求的边数之和,对 998244353998244353 取模。

数据范围

2≤n≤1052\le n\le10^5,1≤ui,vi≤n1\le u_i,v_i\le n。输入保证构成一棵树。

样例 1

5
1 2
2 3
3 5
3 4
16 44 60 0 0

样例 2

8
1 2
2 3
2 4
4 5
4 7
7 8
6 7
51 316 1596 6120 15720 20160 0 0