Problem Statement

This problem shares the "problem setting", "input format and constraints", "number of test cases", and so on with No.1773 Love Triangle, but differs in the "time limit", "output format", "test case generation method", and so on.

There are $N$ stars $1, \dots, N$ shining in the night sky. Among the triples of distinct stars, $M$ 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 record as many great triangles as possible. So you decided to choose any subset $S = \{ T_{i_1}, \dots, T_{i_L} \}$ $(1 \le i_1 < i_2 < \dots < i_L \le k)$ of $\{T_1, \dots, T_k\}$ and build an undirected graph (with $N$ vertices and $3L$ edges) by adding, for each great triangle $T_{i_l}$ $(l = 1, \dots, L)$ in $S$, the corresponding edges $(u_{i_l}, v_{i_l})$, $(v_{i_l}, w_{i_l})$, $(w_{i_l}, u_{i_l})$. 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 (multiple chosen great triangles must not share an edge).

Find the maximum number of elements of $S$ satisfying all of the above conditions. Solve the problem separately for each $k$ of $k = 1, \dots, M$, and output the answers to these problems over $M$ lines.

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 over $M$ lines. On the $i$-th line $(1 \le i \le M)$, output an integer that is the answer to the problem for $k = i$. Also print a newline at the end of the $M$-th line.

Sample

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

1
2
2
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

1
2
3
4
4
4
5
6
6
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

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