bzoj#P2184. 任意图的匹配

任意图的匹配

题目描述

每天都要考,每天都要讲,大家注意力都集中不起来了,每天听解题报告时都有人交头接耳(也包括我,呵呵)。

这样做大大的影响的学习效率(可能吧)。

于是,有些好奇心重的同学就开始研究,怎样才会最吵。培训的总共有 nn 个人,但不是每两人之间都讲话,只有一些人有话题聊,而且一个人可能会和多个人有话题(共 mm 对人)。如果所有同学都说在话,教室里最吵。你的任务就是求出把说话者对数控制在多少人以内,无论如何教室里不会变得最吵?注意:A 和 B 说话,同时 B 和 C 说话,这算两对人说话。

输入格式

多组数据,一直处理到文件末尾,对于每一组数据:

第一行两个整数 n,mn,m

接下来 mm 行,每行两个整数 x,yx,y 表示 xxyy 有话题聊。

输出格式

一行,一个整数表示要把说话者对数控制在多少以内,无论如何教室里不最吵。

样例输入

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

样例输出

2

数据规模与约定

对于 100%100\% 的数据,n103n\leq 10^3m3×103m\leq 3\times 10^3