Problem Statement

This problem shares the "problem setting", "input format and constraints", "number of test cases", etc. with No.1774 Love Triangle (Hard), but differs in the "execution time limit", "output format", "test case generation method", etc.

There are $N$ stars $1, \dots, N$ shining in the night sky. $M$ of the triples of distinct stars are called "great triangles", and the $i$-th great triangle $T_i$ ($1 \le i \le M)$ consists of the stars $(u_i, v_i, w_i)$ $(1 \le u_i < v_i < w_i \le N)$.

You love triangles and want to keep a record of as many great triangles as possible. To do so, you decide to choose an arbitrary subset $S = \{ T_{i_1}, \dots, T_{i_L} \}$ $(1 \le i_1 < i_2 < \dots < i_L \le M)$ of $\{T_1, \dots, T_M\}$ and build an undirected graph (with $N$ vertices and $3L$ edges) by adding the corresponding edges $(u_{i_l}, v_{i_l})$, $(v_{i_l}, w_{i_l})$, $(w_{i_l}, u_{i_l})$ for each great triangle $T_{i_l}$ $(l = 1, \dots, L)$ contained in $S$. However, since you love only triangles, $S$ must satisfy the following conditions:

• The added edges must not form a simple cycle of length other than $3$.
• In particular, there must be no multiple edges (the chosen great triangles must not share an edge).

Find the maximum number of elements of $S$ satisfying all of the above conditions.

Input

$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)$
• All inputs are integers.

Output

Output the integer that is the answer to the problem. Print a newline at the end.

Sample

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