問題文

N 頂点 M 辺の単純無向グラフ G が与えられます。ここで、 \mathrm{NUPC} を以下の図で示すグラフとします。

黒い点はグラフの頂点を、それを結んでいる線分はグラフの辺を表します。

G に \mathrm{NUPC} を点素に埋め込むことのできる数の最大値を求めてください。

すなわち、以下を満たす最大の整数 k を求めてください。

• G は 「 \mathrm{NUPC} が k 個からなるグラフ」を部分グラフとして含む。

制約

• 1 \le N, M \le 10^5
• 1 \leq u_i, v_i \leq N
• G の各連結成分の頂点数は 10 以下
• 与えられるグラフは単純である。すなわち、自己ループや多重辺は存在しない。
• 入力はすべて整数

入力例 1

23 20
1 2
2 3
3 4
4 5
5 6
6 7
8 9
9 10
10 11
11 12
12 13
14 15
15 16
14 17
17 18
18 15
19 20
20 21
21 22
22 23

出力例 1

1

グラフは図のようになっています。このグラフは \mathrm{NUPC} をちょうど 1 個含みます。

入力例 2

23 21
1 2
2 3
3 4
4 5
5 6
6 7
8 9
9 10
10 11
11 12
12 13
14 15
15 16
14 17
17 18
18 15
19 20
20 21
21 22
22 23
14 21

出力例 2

1

グラフは図のようになっています。 1 つの連結成分に 2 つの文字を埋め込むこともできます。

入力例 3

49 60
40 25
40 43
40 31
40 21
7 21
3 25
3 31
3 21
25 43
25 49
21 49
21 39
49 26
39 26
38 8
38 17
41 22
41 8
41 15
22 8
22 15
22 30
8 30
5 15
5 11
15 11
48 11
12 13
29 1
29 44
28 1
28 36
13 10
13 16
13 44
10 36
1 36
36 44
45 32
45 35
32 14
14 33
14 35
33 4
35 4
20 37
20 47
37 9
18 27
18 47
18 23
46 23
46 9
23 9
24 2
24 19
2 34
6 34
6 42
34 42

出力例 3

2