アカベ高校のあるクラスでは、クラスメイトの友達関係を使って、「知り合い」という関係を次のように定めている。
- A さんとB さんが友達なら、A さんとB さんは知り合いである。
- A さんとB さんが友達で、B さんとC さんが知り合いなら、A さんとC さんも知り合いである。
また、「仲間」であるという関係を次のように定めている。
- A さんとB さんが知り合いであって、現在友達である誰か２人のクラスメイトが友達でなくなったとしてもなおA さんとB さんが知り合いであるなら、A さんとB さんは仲間である。
このクラスに最近転校してきたPCK 君は、クラスの人たちを招待してパーティを開こうと考えている。パーティにより多くの人を招待したいと思い、招待リストを作成した。そのとき、PCK 君が転校してくる前の友達関係を利用して、次のような条件をおいた。
T さんが招待リストに入っているとき、
- T さんと仲間であるU さんは招待リストに入っている。
- U さんがT さんと仲間ではない場合、U さんがT さんと友達であるか、U さんがT さんの仲間の誰かと友達であるなら、U さんはリストに入っていない。
PCK 君は、この条件を満たす最大人数のクラスメイトを招待リストに入れた。
クラスメイトの人数N と友達関係が与えられたとき、PCK 君が作ったリストに入っている人の数を求めるプログラムを作成せよ。クラスメイトにはそれぞれ0 からN-1 までの番号が割り当てられているものとする。
Input
入力は以下の形式で与えられる。
N M s1 t1 s2 t2 : sM tM
１行目にクラスメイトの人数N (2 ≤ N ≤ 105)と友達関係の数M (1 ≤ M ≤ 2×105)が与えられる。続くM 行に友達関係を表すクラスメイトの番号si,ti (0 ≤ si,ti ≤ N-1)が与えられる(si≠ti)。これらはクラスメイトsi とクラスメイトti が友達であることを表す。ただし、同じ人どうしの友達関係は２回以上与えられない。
Output
PCK 君が招待したクラスメイトの人数の最大値を１行に出力する。
Sample Input 1
7 8 0 1 1 2 1 3 2 3 0 4 4 5 4 6 5 6
Sample Output 1
6
Sample Input 2
3 2 0 1 1 2
Sample Output 2
2