#include #include #include #include #include #include #include #include using namespace std; using lli = long long int; class rational{ public: rational(){x = 0, y = 1;} rational(lli a, lli b){x = a, y = b;} lli x, y; rational operator+(rational a){ rational r((x*a.y + a.x*y), y*a.y); lli g = gcd(r.x, r.y); r.x /= g, r.y /= g; if(r.y < 0) r.x = -r.x, r.y = -r.y; return r; } rational operator-(rational a){ rational r((x*a.y - a.x*y), y*a.y); lli g = gcd(r.x, r.y); r.x /= g, r.y /= g; if(r.y < 0) r.x = -r.x, r.y = -r.y; return r; } rational operator*(rational a){ rational r(x*a.x, y*a.y); lli g = gcd(r.x, r.y); r.x /= g, r.y /= g; if(r.y < 0) r.x = -r.x, r.y = -r.y; return r; } rational operator/(rational a){ if(a.x == 0){ cerr << "divided by zero." << endl; exit(1); } rational r(x*a.y, y*a.x); lli g = gcd(r.x, r.y); r.x /= g, r.y /= g; if(r.y < 0) r.x = -r.x, r.y = -r.y; return r; } }; mt19937 mt(234298343); // uniform_int_distribution rndgen(0, 49725516559); uniform_int_distribution rndgen(0, 1e9+7-1); int Rank(vector > M){ // for(int i = 0; i < M.size(); i++) { // for(int j = 0; j < M.size(); j++) { // cout << M[i][j].x << "/" << M[i][j].y << " "; // } // cout << endl; // } // cout << endl; // cout << endl; int pivot = 0, r = 0; rational z; for(int i = 0; i < M.size(); i++) { // cout << "i:" << i << ", pivot:" << pivot << ", n:" << M.size() << endl; while(pivot < M.size()){ for(int j = i + 1; j < M.size(); j++) { if(M[j][pivot].x != 0 and M[i][pivot].x == 0) swap(M[i], M[j]); } if(M[i][pivot++].x != 0) break; } if(pivot == M.size() and M[i][pivot - 1].x == 0) break; z = M[i][pivot - 1]; // for(int i = 0; i < M.size(); i++) { // for(int j = 0; j < M.size(); j++) { // cout << M[i][j].x << "/" << M[i][j].y << " "; // } // cout << endl; // } // cout << "piv:" << pivot << ", i:" << i << ", n:" << M.size() << endl; // cout << "z:" << z.x << "/" << z.y << endl; for(int j = 0; j < M.size(); j++) M[i][j] = M[i][j] / z; for(int j = i+1; j < M.size(); j++) { rational w = M[j][pivot - 1]; // cout << "wwww:" << w.x << "/" << w.y << endl; for(int k = 0; k < M.size(); k++) M[j][k] = M[j][k] - (w * M[i][k]); } // cout << endl; // cout << endl; } r = 1e9; for(int i = M.size() - 1; i >= 0 and r == 1e9; i--) { for(int j = 0; j < M.size() and r == 1e9; j++) { if(M[i][j].x != 0) r = i + 1; } } // for(int i = 0; i < M.size(); i++) { // cout << "i: " << setw(2) << i << " "; // for(int j = 0; j < M.size(); j++) { // if(M[i][j].x != 0) cout << "1 "; // else cout << "0 "; // } // for(int j = 0; j < M.size(); j++) { // cout << M[i][j].x << "/" << M[i][j].y << " "; // } // cout << endl; // } return r; } int main(){ int n, m, t = 3; // lli mod = 49725516559; lli mod = 1e9+7; cin >> n >> m; vector > > M(t, vector >(n, vector(n, 0))); for(int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; u--, v--, w--; for(int j = 0; j < t; j++) { lli x = rndgen(mt); M[j][u][v] = (M[j][u][v] + x)%mod; M[j][v][w] = (M[j][v][w] + x)%mod; M[j][w][u] = (M[j][w][u] + x)%mod; M[j][v][u] = (M[j][v][u] - x + mod)%mod; M[j][w][v] = (M[j][w][v] - x + mod)%mod; M[j][u][w] = (M[j][u][w] - x + mod)%mod; } } vector > ratM(n, vector(n)); int ans = 0; for(int k = 0; k < t; k++) { for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { ratM[i][j] = rational(M[k][i][j], 1); } } ans = max(ans, Rank(ratM)); // for(int i = 0; i < n; i++) { // for(int j = 0; j < n; j++) { // ratM[i][j] = rational(1, 1); // } // } // Rank(ratM); } cout << ans/2 << endl; }