← 返回题目列表

AtCoder · arc115_d

D. 奇数度

中文机器翻译题面 查看原题

分数: 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