P3452 [POI 2007] 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$。