Crime

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 262144/131072KB (Java/Others)

Problem Description

发生案件了。。。。Losanto的饭卡不见了。。。
经过观察,警方锁定了n个嫌疑人,打算进行集中审问。。。
只有两个审问的房间,而且使用时间有限,于是警方打算在两个房间里同时对多个嫌疑进行审问。现在警方得到了一张表,表示哪两个嫌疑人互相认识(认识没有传递性,比如A和B认识,B和C认识,不代表A和C认识),为了保证嫌疑人没有相互串通,要求每个房间里的嫌疑人互不认识。。
现在问题来了,警方不知道能不能在两个房间各一次审问中就完成对所有罪犯的审问。
如果可以分组,那么对一组中的一个人询问一个另一组中他认识的人的情况,而另一组中的那个人也会得到相应的这个人的有关问题。而每个人最多被询问一次也可以不询问,最多可以有多少次询问。

Input

多组测试数据,第一行是n和m,表示嫌疑人数目(1<n<=300),和m对认识关系m(0<m<=(n-1)*n/2)
接下来m行,每行有两个字符串a和b,表示名字为a和名字为b的嫌疑人认识(嫌疑人没有重名的,名字长度小于等于10个字母,不保证没有重复的认识关系)。

Output

可以完成分组则输出最多可以有多少次询问,不可以输出No。

Sample Input

4 4 
Jack Tom
Jack David
Jack Lily
Tom David
6 5
Jack Tom
Jack David
Jack Lily
Tom Peter
David Alice

Sample Output

No
6

Source

第九届北京化工大学程序设计竞赛

Manager

Information
Solved Number51
Submit Number137
Problem Tags
graph matchings
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel