#include #define DIM 200 #define M_MAX 600 const int Mod = 19997; int div_mod(int x, int y, int z) { if (x % y == 0) return x / y; else return (div_mod((1 + x / y) * y - x, (z % y), y) * z + x) / y; } int rank_matrix(int d, int A[][DIM]) { if (d <= 0) return 1; int i, j, k, r, p[DIM], X[DIM][DIM], inv, tmp[DIM]; for (i = 0; i < d; i++) p[i] = i; for (i = 0; i < d; i++) { for (j = 0; j < d; j++) { X[i][j] = A[i][j] % Mod; if (X[i][j] < 0) X[i][j] += Mod; } } for (i = 0, r = 0; i < d; i++) { for (j = r; j < d; j++) if (X[i][p[j]] != 0) break; if (j == d) continue; else if (j != r) { p[r] ^= p[j]; p[j] ^= p[r]; p[r] ^= p[j]; } inv = div_mod(1, X[i][p[r]], Mod); for (k = i; k < d; k++) tmp[k] = X[k][p[r]] * inv % Mod; for (j = r + 1; j < d; j++) { if (X[i][p[j]] != 0) { for (k = i + 1; k < d; k++) { X[k][p[j]] -= tmp[k] * X[i][p[j]] % Mod; if (X[k][p[j]] < 0) X[k][p[j]] += Mod; } X[i][p[j]] = 0; } } r++; } return r; } #define MT_N 624 #define MT_M 397 #define MT_MATRIX_A 0x9908b0dfUL #define MT_UPPER_MASK 0x80000000UL #define MT_LOWER_MASK 0x7fffffffUL static unsigned int mt[MT_N]; static int mti = MT_N + 1; void init_genrand(unsigned int s) { mt[0] = s & 0xffffffffUL; for (mti = 1; mti < MT_N; mti++) { mt[mti] = (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti); mt[mti] &= 0xffffffffUL; } } unsigned int genrand() { unsigned int y; static unsigned int mag01[2] = {0x0UL, MT_MATRIX_A}; if (mti >= MT_N) { int kk; if (mti == MT_N + 1) init_genrand(5489UL); for (kk = 0; kk < MT_N - MT_M; kk++) { y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK); mt[kk] = mt[kk+MT_M] ^ (y >> 1) ^ mag01[y&0x1UL]; } for (; kk < MT_N - 1; kk++) { y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK); mt[kk] = mt[kk+(MT_M-MT_N)] ^ (y >> 1) ^ mag01[y&0x1UL]; } y = (mt[MT_N-1] & MT_UPPER_MASK) | (mt[0] & MT_LOWER_MASK); mt[MT_N-1] = mt[MT_M-1] ^ (y >> 1) ^ mag01[y&0x1UL]; mti = 0; } y = mt[mti++]; y ^= (y >> 11); y ^= (y << 7) & 0x9d2c5680UL; y ^= (y << 15) & 0xefc60000UL; y ^= (y >> 18); return y; } void chmax(int* a, int b) { if (*a < b) *a = b; } void naive(int N, int M, int u[], int v[], int w[]) { int i, j, ans = 0, Y[DIM][DIM] = {}, r; for (i = 1; i <= M; i++) { r = genrand() % Mod; Y[u[i]][v[i]] += r; if (Y[u[i]][v[i]] >= Mod) Y[u[i]][v[i]] -= Mod; Y[u[i]][w[i]] -= r; if (Y[u[i]][w[i]] < 0) Y[u[i]][w[i]] += Mod; Y[v[i]][u[i]] -= r; if (Y[v[i]][u[i]] < 0) Y[v[i]][u[i]] += Mod; Y[v[i]][w[i]] += r; if (Y[v[i]][w[i]] >= Mod) Y[v[i]][w[i]] -= Mod; Y[w[i]][u[i]] += r; if (Y[w[i]][u[i]] >= Mod) Y[w[i]][u[i]] -= Mod; Y[w[i]][v[i]] -= r; if (Y[w[i]][v[i]] < 0) Y[w[i]][v[i]] += Mod; chmax(&ans, rank_matrix(N, Y)); printf("%d\n", ans / 2); } } int main() { int i, N, M, u[M_MAX + 1], v[M_MAX + 1], w[M_MAX + 1]; scanf("%d %d", &N, &M); for (i = 1; i <= M; i++) scanf("%d %d %d", &(u[i]), &(v[i]), &(w[i])); naive(N, M, u, v, w); fflush(stdout); return 0; }