← 返回题目列表

Codeforces · 379/G

G. 新年仙人掌

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

杰克和吉尔厌倦了新年树,现在他们家里有了新年仙人掌!仙人掌是一种无向连通图,其中任意两个简单循环至多有一个公共顶点。换句话说,该图没有任何边位于多个简单循环上。

12 月 31 日,他们将在仙人掌的顶点挂上玩具来装饰仙人掌。每个顶点最多会悬挂一个玩具 - 要么是杰克悬挂的玩具,要么是吉尔悬挂的玩具。顶点可能没有玩具。

杰克和吉尔一直在争论,所以他们不希望有任何边连接两个顶点,其中一个顶点有杰克的玩具,另一个顶点有吉尔的玩具。

杰克决定挂一个玩具。如果吉尔和吉尔合作最大化这个值,最多可以悬挂多少个玩具 b?你的任务是编写一个程序,为从 0 到新年仙人掌顶点数的所有 a 找到所需的 b。

输入

第一行包含两个整数 n 和 m (1 ≤ n ≤ 2500, n - 1 ≤ m) — 相应的顶点数和边数。接下来的 m 行包含两个整数 a、b(1 ≤ a,b ≤ n,a ≠ b),这意味着有一条边连接顶点 a и b。任何一对顶点之间至多有一条边。

输出

第一行必须包含空格分隔的 ba(对于所有 0 ≤ a ≤ n),其中 ba 等于仙人掌上吉尔玩具的最大数量,考虑到它有杰克的玩具。数字ba按a递增的顺序排列。

示例

输入 #1

1 0

输出 #1

1 0

输入 #2

16 20
1 2
3 4
5 6
6 7
7 8
9 10
10 11
11 12
13 14
15 16
1 5
9 13
14 10
10 6
6 2
15 11
11 7
7 3
16 12
8 4

输出 #2

16 13 12 12 10 8 8 7 6 4 4 3 3 1 0 0 0

注意

第二个示例中的仙人掌是: