#ifndef LOCAL #pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") #endif #include using namespace std; using ll=long long; #define int ll #define rng(i,a,b) for(int i=int(a);i=int(a);i--) #define per(i,b) gnr(i,0,b) #define pb push_back #define eb emplace_back #define a first #define b second #define bg begin() #define ed end() #define all(x) x.bg,x.ed #define si(x) int(x.size()) #ifdef LOCAL #define dmp(x) cerr<<__LINE__<<" "<<#x<<" "< bool chmax(t&a,u b){if(a bool chmin(t&a,u b){if(b using vc=vector; template using vvc=vc>; using pi=pair; using vi=vc; template ostream& operator<<(ostream& os,const pair& p){ return os<<"{"< ostream& operator<<(ostream& os,const vc& v){ os<<"{"; for(auto e:v)os< void dmpr(ostream&os,const T&t,const Args&... args){ os< ostream& operator<<(ostream&os,const array&a){ return os<(all(a)); } template void print_tuple(ostream&,const T&){ } template void print_tuple(ostream&os,const T&t){ if(i)os<<","; os<(t); print_tuple(os,t); } template ostream& operator<<(ostream&os,const tuple&t){ os<<"{"; print_tuple<0,tuple,Args...>(os,t); return os<<"}"; } ll read(){ ll i; cin>>i; return i; } vi readvi(int n,int off=0){ vi v(n); rep(i,n)v[i]=read()+off; return v; } pi readpi(int off=0){ int a,b;cin>>a>>b; return pi(a+off,b+off); } template void print_single(t x,int suc=1){ cout< void print_single(const pair&p,int suc=1){ print_single(p.a,2); print_single(p.b,suc); } template void print_single(const vector&v,int suc=1){ rep(i,v.size()) print_single(v[i],i==int(v.size())-1?suc:2); } template void print_offset(const vector&v,ll off,int suc=1){ rep(i,v.size()) print_single(v[i]+off,i==int(v.size())-1?suc:2); } template void print_single(const array&v,int suc=1){ rep(i,N) print_single(v[i],i==int(N)-1?suc:2); } template void print(const T&t){ print_single(t); } template void print(const T&t,const Args&...args){ print_single(t,2); print(args...); } string readString(){ string s; cin>>s; return s; } template T sq(const T& t){ return t*t; } void YES(bool ex=true){ cout<<"YES\n"; if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void NO(bool ex=true){ cout<<"NO\n"; if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void Yes(bool ex=true){ cout<<"Yes\n"; if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void No(bool ex=true){ cout<<"No\n"; if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } //#define CAPITAL /* void yes(bool ex=true){ #ifdef CAPITAL cout<<"YES"<<"\n"; #else cout<<"Yes"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void no(bool ex=true){ #ifdef CAPITAL cout<<"NO"<<"\n"; #else cout<<"No"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif }*/ void possible(bool ex=true){ #ifdef CAPITAL cout<<"POSSIBLE"<<"\n"; #else cout<<"Possible"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void impossible(bool ex=true){ #ifdef CAPITAL cout<<"IMPOSSIBLE"<<"\n"; #else cout<<"Impossible"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } constexpr ll ten(int n){ return n==0?1:ten(n-1)*10; } const ll infLL=LLONG_MAX/3; #ifdef int const int inf=infLL; #else const int inf=INT_MAX/2-100; #endif int topbit(signed t){ return t==0?-1:31-__builtin_clz(t); } int topbit(ll t){ return t==0?-1:63-__builtin_clzll(t); } int topbit(ull t){ return t==0?-1:63-__builtin_clzll(t); } int botbit(signed a){ return a==0?32:__builtin_ctz(a); } int botbit(ll a){ return a==0?64:__builtin_ctzll(a); } int botbit(ull a){ return a==0?64:__builtin_ctzll(a); } int popcount(signed t){ return __builtin_popcount(t); } int popcount(ll t){ return __builtin_popcountll(t); } int popcount(ull t){ return __builtin_popcountll(t); } int bitparity(ll t){ return __builtin_parityll(t); } bool ispow2(int i){ return i&&(i&-i)==i; } ll mask(int i){ return (ll(1)< void mkuni(vc&v){ sort(all(v)); v.erase(unique(all(v)),v.ed); } ll rand_int(ll l, ll r) { //[l, r] //#ifdef LOCAL static mt19937_64 gen; /*#else static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count()); #endif*/ return uniform_int_distribution(l, r)(gen); } ll rand_int(ll k){ //[0,k) return rand_int(0,k-1); } template void myshuffle(vc&a){ rep(i,si(a))swap(a[i],a[rand_int(0,i)]); } template int lwb(const vc&v,const t&a){ return lower_bound(all(v),a)-v.bg; } template bool bis(const vc&v,const t&a){ return binary_search(all(v),a); } vvc readGraph(int n,int m){ vvc g(n); rep(i,m){ int a,b; cin>>a>>b; //sc.read(a,b); a--;b--; g[a].pb(b); g[b].pb(a); } return g; } vvc readTree(int n){ return readGraph(n,n-1); } vc presum(const vi&a){ vc s(si(a)+1); rep(i,si(a))s[i+1]=s[i]+a[i]; return s; } //BIT で数列を管理するときに使う (CF850C) template vc predif(vc a){ gnr(i,1,si(a))a[i]-=a[i-1]; return a; } template vvc imos(const vvc&a){ int n=si(a),m=si(a[0]); vvc b(n+1,vc(m+1)); rep(i,n)rep(j,m) b[i+1][j+1]=b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j]; return b; } //verify してないや void transvvc(int&n,int&m){ swap(n,m); } template void transvvc(int&n,int&m,vvc&a,Args&...args){ assert(si(a)==n); vvc b(m,vi(n)); rep(i,n){ assert(si(a[i])==m); rep(j,m)b[j][i]=a[i][j]; } a.swap(b); transvvc(n,m,args...); } //CF854E void rotvvc(int&n,int&m){ swap(n,m); } template void rotvvc(int&n,int&m,vvc&a,Args&...args){ assert(si(a)==n); vvc b(m,vi(n)); rep(i,n){ assert(si(a[i])==m); rep(j,m)b[m-1-j][i]=a[i][j]; } a.swap(b); rotvvc(n,m,args...); } //ソートして i 番目が idx[i] //CF850C template vi sortidx(const vc&a){ int n=si(a); vi idx(n);iota(all(idx),0); sort(all(idx),[&](int i,int j){return a[i] vc a_idx(const vc&a,const vi&idx){ int n=si(a); assert(si(idx)==n); vc vs(n); rep(i,n)vs[i]=a[idx[i]]; return vs; } //CF850C vi invperm(const vi&p){ int n=si(p); vi q(n); rep(i,n)q[p[i]]=i; return q; } template s SUM(const vc&a){ return accumulate(all(a),s(0)); } template t MAX(const vc&a){ return *max_element(all(a)); } template t MIN(const vc&a){ return *min_element(all(a)); } template pair operator+(const pair&a,const pair&b){ return mp(a.a+b.a,a.b+b.b); } vi vid(int n){ vi res(n);iota(all(res),0); return res; } template S getrev(S s){ reverse(all(s)); return s; } pi operator+(pi a,pi b){return pi(a.a+b.a,a.b+b.b);} template t gpp(vc&vs){ assert(si(vs)); t res=move(vs.back()); vs.pop_back(); return res; } //mint107 は verify してねえ //#define DYNAMIC_MOD struct modinfo{uint mod,root; #ifdef DYNAMIC_MOD constexpr modinfo(uint m,uint r):mod(m),root(r),im(0){set_mod(m);} ull im; constexpr void set_mod(uint m){ mod=m; im=ull(-1)/m+1; } uint product(uint a,uint b)const{ ull z=ull(a)*b; uint x=((unsigned __int128)z*im)>>64; uint v=uint(z)-x*mod; return v struct modular{ static constexpr uint const &mod=ref.mod; static modular root(){return modular(ref.root);} uint v; //modular(initializer_listls):v(*ls.bg){} modular(ll vv=0){s(vv%mod+mod);} modular& s(uint vv){ v=vv>=1; } return res; } modular inv()const{return pow(mod-2);} /*modular inv()const{ int x,y; int g=extgcd(v,mod,x,y); assert(g==1); if(x<0)x+=mod; return modular(x); }*/ friend modular operator+(ll x,const modular&y){ return modular(x)+y; } friend modular operator-(ll x,const modular&y){ return modular(x)-y; } friend modular operator*(ll x,const modular&y){ return modular(x)*y; } friend modular operator/(ll x,const modular&y){ return modular(x)/y; } friend ostream& operator<<(ostream&os,const modular&m){ return os<>(istream&is,modular&m){ ll x;is>>x; m=modular(x); return is; } bool operator<(const modular&r)const{return v; #endif using mint=modular; mint parity(int i){ return i%2==0?1:-1; } #ifdef LOCAL const int vmax=10010; #else const int vmax=(1<<21)+10; #endif mint fact[vmax],finv[vmax],invs[vmax]; void initfact(){ fact[0]=1; rng(i,1,vmax){ fact[i]=fact[i-1]*i; } finv[vmax-1]=fact[vmax-1].inv(); for(int i=vmax-2;i>=0;i--){ finv[i]=finv[i+1]*(i+1); } for(int i=vmax-1;i>=1;i--){ invs[i]=finv[i]*fact[i-1]; } } mint choose(int n,int k){ return fact[n]*finv[n-k]*finv[k]; } mint binom(int a,int b){ return fact[a+b]*finv[a]*finv[b]; } mint catalan(int n){ return binom(n,n)-(n-1>=0?binom(n-1,n+1):0); } /* const int vmax=110; mint binbuf[vmax][vmax]; mint choose(int n,int k){ return binbuf[n-k][k]; } mint binom(int a,int b){ return binbuf[a][b]; } void initfact(){ binbuf[0][0]=1; rep(i,vmax)rep(j,vmax){ if(i)binbuf[i][j]+=binbuf[i-1][j]; if(j)binbuf[i][j]+=binbuf[i][j-1]; } } */ mint p2[vmax],p2inv[vmax]; void initp2(){ p2[0]=1; rep(i,vmax-1)p2[i+1]=p2[i]*2; p2inv[vmax-1]=p2[vmax-1].inv(); per(i,vmax-1)p2inv[i]=p2inv[i+1]*2; } template void mat0(vvc&a,int n,int m){ static vvc pool; while(si(a)n)pool.pb(gpp(a)); rep(i,n){ a[i].resize(m); fill(all(a[i]),0); } } //VERIFY: yosupo mint det(vvc&a){ const int n=a.size(); mint ans(1); rep(i,n){ rng(j,i+1,n)if(a[j][i]){ ans=-ans; swap(a[j],a[i]); break; } if(a[i][i]==0)return 0; ans*=a[i][i]; mint z=a[i][i].inv(); rng(j,i+1,n){ mint w=-a[j][i]*z; rng(k,i,n) a[j][k]+=a[i][k]*w; } } return ans; } //inplace //左c列をsweepしする //aの先頭rank行に要素が入っている感じ //Yuhao Du Contest 11 (Ucup1-10 G) //https://uoj.ac/problem/785 int sweep(vvc&a,vi*col=nullptr,int c=-1){ if(a.empty())return 0; if(c==-1)c=a[0].size(); int h=a.size(),w=a[0].size(),r=0; rep(i,c){ if(r==h)break; rng(j,r,h)if(a[j][i]){ swap(a[r],a[j]); break; } if(a[r][i]==0)continue; mint u=a[r][i].inv(); rep(j,h)if(j!=r){ //rng(j,r+1,h){ //for speed up (sweep に使った列に複数の non-zero があっても良い場合) mint z=-a[j][i]*u; rng(k,i,w) a[j][k]+=a[r][k]*z; } if(col)col->pb(i); r++; } return r; } //https://uoj.ac/problem/785 bool inverse(vvc&a){ int n=si(a); rep(i,n){ assert(si(a[i])==n); a[i].resize(2*n); } static vi row; row.resize(n);rep(i,n)row[i]=i; rep(i,n){ rng(j,i,n)if(a[j][i]){ swap(a[i],a[j]); swap(row[i],row[j]); break; } if(a[i][i]==0)return false; mint u=a[i][i].inv(); a[i][n+i]=1; rng(k,i,n+i+1)a[i][k]*=u; rep(j,n)if(j!=i){ mint z=-a[j][i]; rng(k,i,n+i+1)a[j][k]+=a[i][k]*z; } } rep(i,n){ rep(j,n)a[i][row[j]]=a[i][n+j]; a[i].resize(n); } return true; } //https://uoj.ac/problem/785 //mod を減らして定数倍を,改善… void mmm(vvc&c,const vvc&a,const vvc&b){ int n=si(a),m=si(a[0]),l=si(b[0]); assert(m==si(b)); mat0(c,n,l); static vvc tmp;mat0(tmp,n,l); static const int L=15; rep(i,n)rep(j,m)rep(k,l)tmp[i][k]+=ull(a[i][j].v>>L)*(b[j][k].v); rep(i,n)rep(k,l)tmp[i][k]=(tmp[i][k]%mint::mod)< a,inv; Harvey(const vvc&ini):n(si(ini)),a(ini),inv(ini){ bool tmp=inverse(inv); assert(tmp); } using T=tuple; vc buf; void add(int i,int j,mint v){ buf.eb(i,j,v); } vi pos; vvc dif,invss,invst,invts,w,z; //add の結果を使って inv を更新しようとする //正則なら更新に成功し,true が返る //非正則なら a/inv はもとのまま false が返る bool upd(){ pos.clear(); for(auto [i,j,v]:buf){ pos.pb(i); pos.pb(j); } mkuni(pos); int s=si(pos); mat0(dif,s,s); for(auto [i,j,v]:buf) dif[lwb(pos,i)][lwb(pos,j)]+=v; mat0(invss,s,s); rep(i,s)rep(j,s)invss[i][j]=inv[pos[i]][pos[j]]; mmm(w,dif,invss); rep(i,s)w[i][i]+=1; if(!inverse(w)){ buf.clear(); return false; } mat0(invst,s,n); rep(i,s)rep(j,n)invst[i][j]=inv[pos[i]][j]; mat0(invts,n,s); rep(i,n)rep(j,s)invts[i][j]=inv[i][pos[j]]; mmm(z,w,dif); mmm(w,invts,z); mmm(z,w,invst); rep(i,n)rep(j,n) inv[i][j]-=z[i][j]; for(auto [i,j,v]:buf) a[i][j]+=v; buf.clear(); return true; } }; void slv(){ int n,m;cin>>n>>m; vc diag(n); rep(i,n)diag[i]=rand_int(1,mint::mod-1); vvc ini(n,vc(n)); rep(i,n)ini[i][i]=diag[i]; Harvey h(ini); int ans=0; rep(_,m){ int a,b,c;cin>>a>>b>>c; a--;b--;c--; mint v=rand_int(1,mint::mod-1); h.add(a,a,v); h.add(a,c,-v); h.add(b,a,-v); h.add(b,c,v); h.add(a,a,-v); h.add(c,a,v); h.add(a,b,v); h.add(c,b,-v); bool tmp=h.upd(); assert(tmp); rep(i,n)if(diag[i]){ h.add(i,i,-diag[i]); if(h.upd()){ ans++; diag[i]=0; } } assert(ans%2==0); print(ans/2); } } signed main(){ cin.tie(0); ios::sync_with_stdio(0); cout<>t;rep(_,t) slv(); }