描述
乌有世界有着很多国家，这些国家相互之间通过互派使者保持外交联系。然而如果两国间发生了外交风波，则该两国会互相驱逐使者。

如果在发生一些外交事件以后，世界分裂成了两个国家集团，而这两个国家集团之间没有互派使者，那么这个世界将陷入危险的冷战之中。

请你计算出最少发生多少起这样的事件，这个世界就会再次陷入两极格局之中。

输入
第一行包含两个整数n、m，分别代表国家数量和外交关系的数量；接下来m行，每行包含两个国家代号（国家代号的格式为三个大写字母），表示两国之间互派使者。1<=n<=250,m 约为 0.3*(n*(n-1)/2)

输出
一个整数，表示最少发生多少起外交事件，这个世界就会再次陷入两极格局之中。

样例输入
9 17
USB JPA
USB GUK
USB FRC
USB DET
USB CHA
JPA DET
JPA GUK
JPA ROS
GUK FRC
GUK DET
DET FRC
CHA IRA
CHA ROS
CHA KRP
KRP ROS
KRP IRA
ROS IRA

样例输出
2

时间限制
2Sec

内存限制
128MB