UOJ Logo FLYIOI UOJ

FLYIOI

#32. 智力测试(test)

故事背景

Yuyan即将要参加全国一年一度的“谁是百万富翁”大赛。千辛万苦终于来到海选现场,yuyan却要面临着恐怖的智力测试。

题目描述

考官给了yuyan N条钥匙,yuyan要用他们去打开M道门。
对于每扇门,有且最多有两条钥匙可以将其打开;每条钥匙只能用一次;只有打开了第一扇门,才可以打开第二扇门,才可以打开第三道门,以此类推。
yuyan被要求要通过尽量多的门。在yuyan的巨额贿赂下,考官告诉了yuyan每扇门所对应的钥匙。但yuyan的智商还不足以完成这个任务,所以他只得厚着脸皮向你们求助。

输入

第一行两个整数 N (0<=N<=1000) ,M(0<=M<=1000) , 表示N条钥匙和M道门。
接下来 M 行,每行两个整数,表示该门所对应的两条钥匙的编号 (编号从0至N-1 )
注意有的门对应的两条钥匙可能是一样的。

输出

第一行一个整数,表示最多通过的门的个数。

样例输入

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

样例输出

4

数据范围

对于10%的数据,N<=10 , M<=20
对于40%的数据,N<=100 , M<=500
对于100%的数据,N<=1000,M<=1000