#2338. 「HNOI2006」超级英雄

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

题目描述

节目「超级英雄」的大概流程是:选手回答主持人的几个问题,答对问题越多,奖品或奖金越丰厚。主持人准备了若干道题目,选手必须正确回答一道题才能作答下一题,否则就被淘汰。为了增加节目的趣味性并适当降低难度,主持人总会给选手提供几个「锦囊妙计」。

这里,我们稍微改变一下规则。假设主持人总共有 m 道题,选手有 n 种不同的「锦囊妙计」,编号为 0 \sim n-1 。每种「锦囊妙计」只能用一次。每道题都只有两种「锦囊妙计」可以使用(两者可能一样),但每道题只能使用一种「锦囊妙计」。假设一道题使用了它允许的锦囊妙计后,就一定能正确回答,顺利进入下一题。

现在我来到了节目现场,可是我蠢得一道题都不会,只好每道题都借助「锦囊妙计」来过关。如果我事先知道每道题能够使用哪两种「锦囊妙计」,那么你能告诉我怎样选择才能通过最多的题数吗?

输入格式

输入文件的一行是两个正整数 n m ( 1 \leq n \leq 1000, 1 \leq m \leq 1000 ) 。
以下的 m 行,每行两个数,分别表示第 m 个问题可以使用的「锦囊妙计」的编号。

输出格式

第一行为最多能通过的题数 p

样例

样例输入

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

样例输出

4

数据范围与提示

1 \leq n \leq 1000, 1 \leq m \leq 1000