杰克和吉尔厌倦了新年树,现在他们家里有了新年仙人掌!仙人掌是一种无向连通图,其中任意两个简单循环至多有一个公共顶点。换句话说,该图没有任何边位于多个简单循环上。
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
注意
第二个示例中的仙人掌是: