問題文

本問題は No.1774 Love Triangle (Hard) と「問題設定」「入力の形式や制約」「テストケース数」等が共通していますが，「実行時間制限」「出力形式」「テストケース生成方法」等が異なります．

夜空に光る $N$ 個の星 $1, \dots, N$ があります．相異なる星の三つ組のうち $M$ 個は「大三角」と呼ばれ，$i$ 個目の大三角 $T_i$（$1 \le i \le M)$ は星 $(u_i, v_i, w_i)$ $(1 \le u_i < v_i < w_i \le N)$ からなります．

三角形が大好きなあなたはできるだけ多くの大三角を記録に残すため，$\{T_1, \dots, T_M\}$ の部分集合 $S = \{ T_{i_1}, \dots, T_{i_L} \}$ $(1 \le i_1 < i_2 < \dots < i_L \le M)$ を任意に選び，$S$ に含まれる各大三角 $T_{i_l}$ $(l = 1, \dots, L)$ について対応する辺 $(u_{i_l}, v_{i_l})$, $(v_{i_l}, w_{i_l})$, $(w_{i_l}, u_{i_l})$ を張った（$N$ 頂点 $3L$ 辺の）無向グラフを作ることにしました．ただし，あなたは三角形だけが好きなので，$S$ は以下の条件を満たさなければなりません：

• 張られた辺によって長さ $3$ 以外の単純閉路ができてはならない．
• 特に，多重辺が存在してはならない（選ばれた複数の大三角が辺を共有してはならない）．

上記の条件を全て満たすような $S$ の要素数の最大値を求めてください．

入力

$N\ M$
$u_1\ v_1\ w_1$
$\vdots$
$u_M\ v_M\ w_M$

• $3 \le N \le 500$
• $1 \le M \le \min(1000, N(N - 1)(N - 2)/6)$
• $1 \le u_i < v_i < w_i \le N$ $(i = 1, \dots, M)$
• $(u_i, v_i, w_i) \ne (u_j, v_j, w_j)$ $(i \ne j)$
• 入力は全て整数

出力

問題の答えとなる整数を出力してください．末尾で改行してください．

サンプル

8 4
1 2 3
2 4 5
3 5 6
1 3 7

3

15 10
5 6 9
6 10 13
3 12 13
2 7 10
3 4 9
2 10 14
2 5 15
1 12 14
1 2 10
8 11 15

7

39 34
6 12 16
5 22 25
4 16 29
27 28 39
17 26 39
31 36 37
16 34 39
13 24 31
2 9 11
3 19 20
32 37 38
4 7 37
34 35 38
1 7 16
11 31 33
4 7 31
2 7 15
9 11 38
16 27 35
28 32 35
14 23 38
4 16 34
3 9 38
16 25 31
14 16 30
4 22 24
12 25 27
20 22 31
8 17 27
19 32 38
14 19 38
3 23 34
3 9 32
10 21 29

18