D1 - Friends

頂点 辺の単純無向グラフがあります。 番目の辺では と を結びます。 くしらくんはこの中から以下の条件を満たすいくつかの頂点を選びます。

• 選んだ頂点の数を として、選んだ頂点を とした時、を満たす全ての について、 と を直接結ぶ辺が存在する。

くしらくんが選ぶことが出来る頂点の数の最大値を答えてください。

• 各頂点の次数は 以下
• 入力はすべて整数

入力は以下の形式で標準入力から与えられる。

答えを出力してください。

• 入力

4 4
1 2
1 3
1 4
2 3

• 出力

3

頂点 を選ぶことができます。 つ以上の頂点数を選ぶことが出来ないので、 を出力します。

• 入力

4 3
1 2
2 3
3 4

• 出力

2