题解

题面描述

终端部门为了对穿戴设备进行交叉测试，目前有$n$名员工投入测试，人员从$1$到$n$依次编号。为了充分测试和暴露问题，要求任何两个以前戴过同一穿戴设备的人不能再次测同一设备。下面会给出测试投入的人数和测过同一台设备的人员编号，请按照此关系，计算这次至少需要几台穿戴设备供测试。

解题思路

将员工和他们之前使用相同设备的关系建模为图的顶点和边，通过应用DSATUR图着色算法，为每个员工分配不同的颜色，确保任何两个曾共同使用过设备的员工不会分配到相同的颜色。最终，通过确定所需的最少颜色数，即可得到测试所需的最少穿戴设备数量。

题目内容

终端部门为了对穿戴设备进行交叉测试，目前有$n$名员工投入测试，人员从$1$到$n$依次编号。为了充分测试和暴露问题，要求任何两个以前戴过同一穿戴设备的人不能再次测同一设备。下面会给出测试投入的人数和测过同一台设备的人员编号，请按照此关系，计算这次至少需要几台穿戴设备供测试

输入描述

第一行，一个整数$n(1<n<100)$，表示参加测试的人数，人员从$1$到$n$依次编号。

第二行，一个整数$m$，表示接下来有$m$行数据，$1<=m<=C(n,2)$

以下$m$行每行的格式为:两个整数$a，b，$分别表示员工$a$和$b$，用空格分开$(1<=a,b<=n)$表示员工$a$与员工$b$以前测过同一穿戴设备。

输出描述

输出为一个整数，表示至少需要几台穿戴设备供测试。

样例1

输入

5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
3 5

输出

4

说明

$5$个人投入，用连线标记以前测过同一设备的人的关系，不能再测相同设备用颜色标记，可以看出至少需要$4$台穿戴设备供测试

样例2

输入

5
10 
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

输出

5

说明

$5$个人投入，用连线标记以前测过同一设备的人的关系，不能再测相同设备用颜色标记，测过同一设备的人较多，可以看出至少需要$5$台穿戴设备供测试