题目描述(ID:12401)
标题: 超级英雄
标签: 图结构 二分图 二分图匹配
详情:
节目「超级英雄」的大概流程是:选手回答主持人的几个问题,答对问题越多,奖品或奖金越丰厚。主持人准备了若干道题目,选手必须正确回答一道题才能作答下一题,否则就被淘汰。为了增加节目的趣味性并适当降低难度,主持人总会给选手提供几个「锦囊妙计」。
这里,我们稍微改变一下规则。假设主持人总共有 m 道题,选手有 n 种不同的“锦囊妙计”,编号为 0~n−1。每种「锦囊妙计」只能用一次。每道题都只有两种「锦囊妙计」可以使用(两者可能一样),但每道题只能使用一种「锦囊妙计」。假设一道题使用了它允许的锦囊妙计后,就一定能正确回答,顺利进入下一题。
现在我来到了节目现场,可是我蠢得一道题都不会,只好每道题都借助「锦囊妙计」来过关。如果我事先知道每道题能够使用哪两种「锦囊妙计」,那么你能告诉我怎样选择才能通过最多的题数吗?
输入格式:
输入文件的一行是两个正整数 n 和 m (1≤n≤1000,1≤m≤1000) 。
以下的 m 行,每行两个数,分别表示第 m 个问题可以使用的「锦囊妙计」的编号。
输出格式:
第一行为最多能通过的题数 p。
限制: 1≤n≤1000,1≤m≤1000。
样例:

输入

5 6
3 2
2 0
0 3
0 4
3 2
3 2

输出

4
登录并解答