D - 派閥 解説 /

実行時間制限: 2 sec / メモリ制限: 64 MB

問題文

神からの財産と、母音を取り戻した高橋くんは、AtCoder国の腐敗した政治を正すため、国会議員となろうと決めました。
もともと人心掌握術とスピーチに定評があった高橋くんは、何の苦労をすることもなく当選しました。
しかし、議員になってからが本番です。国を正すためには、首相に任命される必要があります。

AtCoder国には高橋くんを除いて N 人の国会議員と、M 個の人間関係 (x,\ y) が存在します。
人間関係 (x,\ y) とは、議員 x と議員 y が知り合いであることを意味します。
高橋くんは N 人の議員から何人かを選んで派閥を作ろうと企んでいます。
派閥に含まれるすべての議員は互いに知り合いでなければなりません。
高橋くんが作成することができる最大の派閥に属する議員数を求めるプログラムを書いてください。

入力

入力は以下の形式で標準入力から与えられる。 
N M
x_1 y_1
x_2 y_2
:
x_M y_M
  1. 1 行目には、高橋くん以外の国会議員の数 N\ (1≦N≦12) と、人間関係の数 M (0≦M≦N(N-1)/2) が半角空白区切りで与えられる。
  2. 2 行目から M+1 行目までの M 行で、人間関係が与えられる。
    • 各議員は 1 から N までの整数で番号がつけられている。
    • 2 行目を基準とした第 i\ (1≦i≦M) 行において、議員 x_i と議員 y_i は知り合いであることを意味する。
    • x_i と y_i はともに整数で、 1 ≦ x_i < y_i ≦ N を満たす。
    • i≠j のとき、(x_i,\ y_i)≠(x_j,\ y_j) であることが保証されている。

出力

高橋くんが作成することができる最大の派閥に属する議員数を 1 行で出力してください。
また、出力の末尾には改行を入れること。

入力例 1

5 3
1 2
2 3
1 3
  • 1 行目：5 人の議員と 3 つの人間関係が存在する。
  • 2 行目：議員 1 と議員 2 は知り合いである。
  • 3 行目：議員 2 と議員 3 は知り合いである。
  • 4 行目：議員 1 と議員 3 は知り合いである。

出力例 1

3
  • 議員 1、議員 2、議員 3 は互いに知り合いなので、この 3 人は派閥を構成することができる。

入力例 2

5 3
1 2
2 3
3 4

出力例 2

2
  • 議員数 2 の派閥として
    1. 議員 1 と議員 2 の派閥
    2. 議員 2 と議員 3 の派閥
    3. 議員 3 と議員 4 の派閥
    の 3 通りが考えられます。

入力例 3

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

出力例 3

4

入力例 4

12 0

出力例 4

1
  • たとえ 12人の議員がいても、誰も知りあいでなければ 1 人からなる派閥しか作成することはできません。