New Year Cactus

题意翻译

厌倦了每年的新年树，Jack和Jill打算在家里种上一棵新年仙人掌！定义一张图为仙人掌，当且仅当其上的每一条边都至多属于一个简单环。 在12.31， 它们两个将在仙人掌上挂上玩具。每个节点上至多只能悬挂一个玩具（Jack的或Jill的），也可以不挂。 由于两人发生了一些不愉快，所以他们不希望仙人掌上存在一条边，使得其一端的节点挂了其中一个人的玩具，另一端挂了另一个人的玩具。 你的问题是，当Jack选择挂a个玩具时，Jill最多能挂多少个玩具？ 请对于所有的a∈[0,n] （n为仙人掌的节点数） 找到一个答案b 。 输入： 第一行两个数n,m($1 <= n <= 2500, n - 1 <= m$ ) 接下来m行，每行两个数a,b，表示两个节点中间有一条边。数据无重边自环。 输出： 一行， n+1个数，分别代表Jack选择悬挂0，1，2，....n个玩具时，Jill最多能悬挂的玩具数目。

题目描述

Jack and Jill are tired of the New Year tree, now they've got a New Year cactus at home! A cactus is a connected undirected graph where any two simple cycles have at most one common vertex. In other words, this graph doesn't have any edges that lie on more than one simple cycle. On the 31st of December they are going to decorate the cactus by hanging toys to its vertices. At most one toy is going to hang on each vertex — it's either the toy Jack hung or the toy Jill hung. It's possible for a vertex to have no toys. Jack and Jill has been arguing, so they don't want any edge to connect two vertices where one vertex has Jack's toy and the other vertex has Jill's toy. Jack has decided to hang $ a $ toys. What maximum number of toys $ b $ can Jill hang if they both cooperate to maximize this value? Your task is to write a program that finds the sought $ b $ for all $ a $ from 0 to the number of vertices on the New Year Cactus.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1<=n<=2500,n-1<=m $ ) — the number of vertices and the number of edges, correspondingly. The next $ m $ lines contain two integers $ a $ , $ b $ each ( $ 1<=a,b<=n,a≠b $ ) that mean that there is an edge connecting vertices $ a $ и $ b $ . Any pair of vertices has at most one edge between them.

输出格式

The first line must contain space-separated $ b_{a} $ (for all $ 0<=a<=n $ ) where $ b_{a} $ equals the maximum number of Jill's toys on the cactus considering that it has $ a $ Jack's toys. Numbers $ b_{a} $ go in the order of increasing $ 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 

说明

The cactus from the second example is: