#P0831. 部落冲突

部落冲突

题目描述

礼尚往来

在大陆上有nn个国家,国家之间经常相互进谏并献上国礼以表友好,但有些国家却不懂礼尚往来的江湖规矩,导致大陆上出现了许多敌对 关系。对于两个国家AA和BB,如果AA向BB进谏并献上国礼,且BB向AA进谏并回礼,AA和BB两个国家就是朋友;而如果AA向BB进谏并献上国礼,但BB未向AA进谏并回礼,AA和BB两个国家将成为敌人。

此外,大陆上还有一个潜规则:

  • 一个国家的朋友的朋友就是这个国家的朋友。
  • 一个国家的敌人的敌人也是这个国家的朋友。

不久后,由于粮食短缺,大陆上发生了战争,现在要建立部落联盟:如果两个国家想在一个部落中,他们两个必须是朋友。

如果一个部落中的国家越多,部落的势力就越大。如果一个部落的势力过于壮大,可能会威胁到大陆首领的地位,因此现在,大陆的首领想知道:在当前发生的所有进谏的基础上,大陆上的国家最大能建立势力多大的部落呢?

输入格式

第一行输入两个整数n(1≤n≤2000),m(1≤m≤2×105)n(1 \le n \le 2000), m(1 \le m \le 2 \times 10^5),表示大陆上国家的数量和进谏的次数。

接下来mm行,每行输入两个整数u,v(1≤u,v≤n)u, v(1 \le u, v \le n),表示国家uu向国家vv进谏并献上国礼。题目保证任何一个国家都不会向一个相同的国家进谏超过一次,且不存在自己向自己进谏的情况。

题目保证不存在aa和bb是朋友的同时aa和bb是敌人的情况。

输出格式

输出一个整数,大陆上势力最大的部落中的国家数。

样例

5 7
1 2
2 3
3 2
2 1
4 5
5 4
4 1
3
6 6
2 3
1 5
5 2
3 2
4 6
6 4
3

提示

对于样例1:11和22是朋友,22和33是朋友,44和55是朋友,44和11是敌人 ⇒\Rightarrow 11、22、33是一个部落,44和55是一个部落。

对于样例2:22和33是朋友,11和55是敌人,55和22是敌人,44和66是朋友 ⇒\Rightarrow 11、22、33是一个部落,44和66是一个部落,55是一个部落。