G - Mixture Drug

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 600

問題文

イルカの手元には 1 から N までの番号が付いた N 種類の薬品があります。
また、薬品の取り扱いについて書かれたリストが手元にあります。
このリストには M 個の項目があり、リストの上から i(1≦i≦M) 番目の項目には「番号 a_i と 番号 b_i の薬品を混合すると毒が発生する。」と書いてあります。

イルカは、リストに基づいて毒が発生しないように、できる限り多くの種類の薬品を混合したいと考えています。
イルカは最大で何種類の薬品を混合できますか?

制約

  • 1≦N≦40
  • 0≦M≦N(N-1)/2
  • 1≦a_i<b_i≦N
  • a_i≠a_j または b_i≠b_j (1≦i<j≦M)
  • 入力は全て整数である。

入力

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

N M 
a_1 b_1 
: 
a_M b_M 

出力

イルカが混合できる薬品の最大種類数を出力せよ。


入力例 1

4 1
1 2

出力例 1

3

番号 1 と番号 2 の薬品を混合すると毒が発生するので、全ての薬品を混合することはできません。
一方で、番号 1 と番号 3 と番号 4 の薬品を混合した場合には、毒が発生しません。
したがって、最大 3 種類の薬品が使えるので、3 と出力します。


入力例 2

1 0

出力例 2

1

入力例 3

20 16
1 8
1 16
2 19
3 5
3 10
5 7
5 13
6 9
7 8
7 11
7 14
7 15
8 12
9 12
9 17
15 20

出力例 3

12