logo AlgoBeat OnlineJudge
登录 注册

#101006. [BZOJ 1006] [HNOI2008]神奇的国度

内存限制:162 MiB 时间限制:20000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

K 国是一个热衷三角形的国度,连人的交往也只喜欢三角原则。他们认为三角关系:即 A 和 B 相互认识,B 和 C 相互认识,C 和 A 相互认识,是简洁高效的。

为了巩固三角关系,K 国禁止四边关系,五边关系等等的存在。所谓 边关系,是指 个人 。之间仅存在 对认识关系:,而没有其它认识关系。比如四边关系指 A、B、C、D 四个人 A 和 B、B 和 C、C 和 D、D 和 A 相互认识,而 A 和 C、B 和 D 不认识。

全民比赛时,为了防止作弊,规定任意一对相互认识的人不得在一队,国王想知道,最少可以分多少支队。

输入格式

第一行两个整数 ,表示有 个人, 对认识关系。

接下来 行每行输入一对朋友。

输出格式

输出一个整数,最少可以分多少队。

样例

样例输入 #1

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

样例输出 #1

3

样例解释

一种方案

数据范围与提示

对于 的数据,