1363_敌友不分

钟Sir不幸被任命为班主任，而且是2个班。总所周知，班里的人，总有些人关系好一点，天天黏在一起，是朋友；有些人关系差一点，比如争夺女朋友，争当班干部，争各种奖项，人品问题等等，存在冲突关系，于是成为敌人。虽说没有永远的朋友，也没有永远的敌人，但钟Sir安排宿舍的时候，就要尽量避免把敌人们安排住同一宿舍（那还不天天打架啊，班主任就永无宁日了），上课的时候就尽量安排他们坐在不同的区域。这样的情况，可以提炼成为下面的模型：

已知集合A={ a₁, a₂, …… a_n }，及集合上的关系 R = { ( a_i, a_j ) | a_i, a_j ∈ A , i ≠ j }，其中( a_i , a_j ) 表示 a_i 与 a_j 间存在冲突关系。要求将A划分成互不相交的子集A₁ , A₂, …… A_k, ( k ≤ n )，使任何子集中的元素均无冲突关系，同时要求划分的子集的个数尽可能少。

例 A = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }

R={ (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) }

可行的子集划分为：A₁ = { 1, 3, 4, 8 }
 A₂ = { 2, 7 }
 A₃ = { 5 }
 A₄ = { 6, 9 }，子集数=4

另一种方案是：A₁ = {1, 3, 5, 8}，A₂ = {2, 4, 7}，A₃ = {6, 9}，子集数=3 。

第一行是2个整数 n （ 0 < n < 1000 ） 和 m ( 0 ≤ m < 9000 )，n表示集合中元素的个数。集合中的元素以1开始的自然数表示。

下面接着m行，每行两个整数，表示这两个元素之间存在冲突。

输出最少的子集划分个数。

9 13
2 8
9 4
2 9
2 1
2 5
6 2
5 9
5 6
5 4
7 5
7 6
3 7
6 3

3