[POI2007]BIU-Offices

题意翻译

## 题目描述 Bytel 是一家移动通信公司。该公司的每位员工都收到了一部公司生产的电话,电话的通讯录中存储着一些同事的电话号码(每部手机中也都有该手机本身的电话号码)。 由于业务扩张,公司总部需要迁移至新的办公区。为了提高工作效率,董事会决定在不同栋楼工作的每一对员工需要**相互**知道对方的电话号码。即如果 $u$ 和 $v$ 在不同的楼工作,则 $u$ 的通讯录里需要存储 $v$ 的电话号,$v$ 的通讯录里也要存储 $u$ 的电话号码。 同时,董事会决定租用尽可能多的楼,以确保良好的工作条件。现在你需要帮助 Bytel 公司计算出他们需要租用多少栋楼。 ## 输入格式 输入第一行包含两个整数 $n,m$,分别代表公司的员工数和通讯录的信息数,员工从 $1$ 到 $n$ 编号。 接下来 $m$ 行,每行两个整数 $a_i,b_i$,表示 $a_i$ 和 $b_i$ **相互**知道对方的电话号码,保证任意两条信息不重复。 ## 输出格式 输出第一行包含一个整数 $t$:董事会需要租用多少栋办公楼。 第二行包含 $t$ 个整数,第 $i$ 个整数 $c_i$ 表示在第 $i$ 栋建筑工作的员工数量。你的输出需要保证 $c_i$ 是单调不下降的。 如果有多种合法方案,你可以输出任意一种。 ## 数据范围 $2 \leq n \leq 10^5$,$1 \leq m \leq 2 \times 10^6$,$1 \leq a_i \lt b_i \leq n$。

题目描述

Bytel is a mobile telephony potentate. Each employee has been issued a company phone, the memory ofwhich holds the numbers of some of his co-workers (all of them have his number in their phones as well). Due to dynamic growth of their operations the board of directors intends to move company headquaters tonew office buildings. It has been decided - in order to boost work efficiency - that every pair of employeesworking in different buildings should know (reciprocally) each others phone number i.e. the memory of theircompany phone ought to hold necessary phone numbers. Simultaneously, the board have decided to rent as many office buildings as possible to ensure good workingconditions. Help the board of Bytel to plan the number of office buildings and their size in accordancewith the aforementioned requirements. ## Task Write a programme which: reads the description of employees' phone number lists from the standard input calculates the maximal number of office buildings and their sizes, satisfying board's conditions writes the outcome to the standard output.

输入输出格式

输入格式


The first line of the standard input consists of two integers: $n$ and $m$ ($2 \le n \le 100\ 000$, $1 \le m \le 2\ 000\ 000$),separated by single spaces, denoting the number of Bytel employees and the number of pairs of employeeswho have their numbers in company phones, respectively. The employees are numbered from $1$ to $n$. Each of the following $m$ lines contains a single pair of integers $a_i$ and $b_i$ ($1 \le a_i < b_i \le n$ for $1 \le i \le m$), separated by a single space, denoting that employees $a_i$ and $b_i$ have their numbers (reciprocally) in company phones' memory. Each pair of integers denoting a pair of employees shall occur once at the most in the standard input.

输出格式


The first line of the standard output should contain a single integer: the maximal number of office buildingsthat Bytel should rent. The second should contain a non-decreasing sequence of positive integers, separatedby singe spaces, denoting the sizes of the office buildings (i.e. the numbers of employees working there). Should there exist more than one correct answer - write out any one of them.

输入输出样例

输入样例 #1

7 16
1 3
1 4
1 5
2 3
3 4
4 5
4 7
4 6
5 6
6 7
2 4
2 7
2 5
3 5
3 7
1 7

输出样例 #1

3
1 2 4