| Good Bye 2013 |
|---|
| Закончено |
Джеку и Джилл надоела традиционная новогодняя елка, теперь у них стоит дома новогодний кактус! Кактус — это такой связный неориентированный граф, в котором любые два простых цикла имеют не более одной общей вершины, другими словами в этом графе не существует ребер, лежащих более чем на одном простом цикле.
31-го декабря они собираются нарядить этот кактус, подвешивая игрушки на его вершины. На каждой вершине может висеть не более одной игрушки — либо висеть будет игрушка, которую повесил Джек, либо игрушка, которую повесила Джилл. Возможно, что на вершине вообще не будет игрушек.
Так как они недавно неполадили, то они не хотят, чтобы какое-либо ребро соединяло две вершины, на одной из которых игрушка Джека, а на другой — игрушка Джилл.
Джек уже решил, что он повесит a игрушек. Какое максимальное количество игрушек b сможет повесить Джилл, если они действуют сообща с целью максимизировать это значение? Ваша задача написать программу, которая находит искомое b для всех a от 0 до количества вершин новогоднего кактуса.
В первой строке содержится два целых числа n и m (1 ≤ n ≤ 2500, n - 1 ≤ m) — количество вершин и ребер новогоднего кактуса. В следующих m строках записаны по два целых числа a, b (1 ≤ a, b ≤ n, a ≠ b) означающие, что очередное ребро соединяет вершины a и b. Между любой парой вершин не более одного ребра.
В первой строке должны быть записаны ba (для всех 0 ≤ a ≤ n) разделенные пробелом, где ba равно максимальному количеству игрушек Джилл на кактусе при условии, что на кактусе повешено a игрушек Джека. Числа ba выводите в порядке увеличения a.
1 0
1 0
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
16 13 12 12 10 8 8 7 6 4 4 3 3 1 0 0 0
Кактус из второго примера изображен на рисунке:
