分数: 600 点
问题陈述
给定一个简单的无向图 N 顶点和 M 边,其中顶点编号 1, \ldots, N 和 i第一条边连接顶点 A_i 和顶点 B_i。对于每个 K(0 \leq K \leq N),精确地找到跨越子图(※)的数量 K 具有奇数度数的顶点。由于答案可能很大,因此将其模数打印出来 998244353.
(※) 子图 H of G 据说是一个跨越子图 G 当顶点集合为 H 等于顶点集 G 和边缘集 H 是边集的子集 G.
约束
- 1 \leq N \leq 5000
- 0 \leq M \leq 5000
- 1 \leq A_i , B_i \leq N
- 给定的图很简单,即它不包含自环,也不包含多边。
输入
输入由标准输入按以下格式给出:
N M A_1 B_1 A_2 B_2 : A_M B_M
输出
打印 N+1 行。的 i- 第行应包含以下问题的答案 K=i-1.
ans_0 ans_1 : ans_N
示例输入 1
3 2 1 2 2 3
示例输出 1
1 0 3 0
每个生成子图具有以下数量的奇数度顶点:
- 没有边的子图有 0 具有奇数度数的顶点;
- 仅有边连接的子图 1 和 2 有 2 具有奇数度数的顶点;
- 仅有边连接的子图 2 和 3 有 2 具有奇数度数的顶点;
- 具有两条边的子图有 2 具有奇数度数的顶点。
示例输入 2
4 2 1 2 3 4
示例输出 2
1 0 2 0 1