// iostream is too mainstream #include // bitch please #include #include #include #include #include #include #include #include #include #include #include #include #define dibs reserve #define OVER9000 1034567890 #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++) #define tisic 47 #define soclose 1e-9 #define chocolate win // so much chocolate #define patkan 9 #define ff first #define ss second #define abs(x) ((x < 0)?-(x):x) #define uint unsigned int #define dbl long double using namespace std; // mylittledoge /* Edmonds' blossom algorithm match[v]: vertex matched to it / -1 finds a tree of alternating paths rooted at R; the parent of v is prev[v] or match[v] also builds a tree of blossoms 'k, I say blossoms, but each blossom = its base */ // based on https://sites.google.com/site/indy256/algo/edmonds_matching int lca(vector &cur_blossom, vector &match, vector &prev, int u, int v) { // in the tree of blossoms // lists blossoms on paths to the root, finds the first common one set blossoms_visited; int b =cur_blossom[u]; while(true) { blossoms_visited.insert(b); if(match[b] == -1 || prev[match[b]] == -1) break; b =cur_blossom[prev[match[b]]];} b =cur_blossom[v]; while(true) { if(blossoms_visited.find(b) != end(blossoms_visited)) return b; b =cur_blossom[prev[match[b]]];} return b;} int find_aug_path(vector< vector > &G, vector &match, vector &prev, int R) { int N =G.size(); vector vis(N,false); vector cur_blossom(N); for(int i =0; i < N; i++) cur_blossom[i] =i; queue q; q.push(R); vis[R] =true; while(!q.empty()) { ALL_THE(G[q.front()],it) if(*it != match[q.front()]) { // in the same blossom, already processed if(cur_blossom[*it] == cur_blossom[q.front()]) continue; if(prev[*it] == -1 && !(match[*it] != -1 && prev[match[*it]] != -1)) { if(*it == R) continue; prev[*it] =q.front(); if(match[*it] == -1) return (*it); // augmenting path to *it vis[match[*it]] =true; q.push(match[*it]); continue;} if(*it != R && !(match[*it] != -1 && prev[match[*it]] != -1)) continue; // blossom found int new_blossom =lca(cur_blossom,match,prev,q.front(),*it); vector in_new_blossom(N,false); int v =q.front(), parent_v =*it; while(cur_blossom[v] != new_blossom) { in_new_blossom[cur_blossom[v]] =in_new_blossom[cur_blossom[match[v]]] =true; prev[v] =parent_v; parent_v =match[v]; v =prev[match[v]];} v =*it, parent_v =q.front(); while(cur_blossom[v] != new_blossom) { in_new_blossom[cur_blossom[v]] =in_new_blossom[cur_blossom[match[v]]] =true; prev[v] =parent_v; parent_v =match[v]; v =prev[match[v]];} for(int i =0; i < N; i++) if(in_new_blossom[cur_blossom[i]]) { cur_blossom[i] =new_blossom; if(vis[i]) continue; vis[i] =true; q.push(i);} } q.pop();} return -1;} vector find_winning(vector< vector > &G, vector &match, vector &prev, int R) { // find all vertices ending at even length alternating paths int N =G.size(); vector is_winning(N,false); is_winning[R] =true; vector vis(N,false); vector cur_blossom(N); for(int i =0; i < N; i++) cur_blossom[i] =i; queue q; q.push(R); vis[R] =true; while(!q.empty()) { ALL_THE(G[q.front()],it) if(*it != match[q.front()]) { // in the same blossom, already processed if(cur_blossom[*it] == cur_blossom[q.front()]) continue; if(prev[*it] == -1 && !(match[*it] != -1 && prev[match[*it]] != -1)) { if(*it == R) continue; prev[*it] =q.front(); vis[match[*it]] =true; is_winning[match[*it]] =true; q.push(match[*it]); continue;} if(*it != R && !(match[*it] != -1 && prev[match[*it]] != -1)) continue; // blossom found int new_blossom =lca(cur_blossom,match,prev,q.front(),*it); vector in_new_blossom(N,false); int v =q.front(), parent_v =*it; while(cur_blossom[v] != new_blossom) { in_new_blossom[cur_blossom[v]] =in_new_blossom[cur_blossom[match[v]]] =true; prev[v] =parent_v; parent_v =match[v]; v =prev[match[v]];} v =*it, parent_v =q.front(); while(cur_blossom[v] != new_blossom) { in_new_blossom[cur_blossom[v]] =in_new_blossom[cur_blossom[match[v]]] =true; prev[v] =parent_v; parent_v =match[v]; v =prev[match[v]];} for(int i =0; i < N; i++) if(in_new_blossom[cur_blossom[i]]) { cur_blossom[i] =new_blossom; is_winning[i] =true; if(vis[i]) continue; vis[i] =true; q.push(i);} } q.pop();} return is_winning;} int main() { cin.sync_with_stdio(0); cin.tie(0); int T; cin >> T; for(int t =0; t < T; t++) { int N,M; cin >> N >> M; vector< vector > G(N); for(int i =0; i < M; i++) { int a,b; cin >> a >> b; G[--a].push_back(--b); G[b].push_back(a);} // random maximal matching vector match(N,-1); int ans =0, matching_sz =0; while(true) { // find all vertices that can matched vector v; for(int i =0; i < N; i++) if(match[i] == -1) { bool m =false; // can it be matched? ALL_THE(G[i],it) if(match[*it] == -1) m =true; if(m) v.push_back(i);} if(v.empty()) break; // is maximal int x =v[rand()%v.size()]; vector w; ALL_THE(G[x],it) if(match[*it] == -1) w.push_back(*it); int y =w[rand()%w.size()]; // match edge x-y matching_sz++; match[x] =y; match[y] =x;} // make it maximum for(int i =0; i < N; i++) if(match[i] == -1) { vector prev(N,-1); int akt =find_aug_path(G,match,prev,i); // end of the found aug. path // cout << i << " " << akt << " "; // for(int j =0; j < N; j++) cout << prev[j] << " "; // cout << endl; if(akt == -1) continue; while(akt != -1) { int prev_akt =match[prev[akt]]; match[akt] =prev[akt]; match[prev[akt]] =akt; akt =prev_akt;} matching_sz++;} // cout << 2*matching_sz << " " << N << "\n"; vector is_winning(N,false); for(int i =0; i < N; i++) if(match[i] == -1) { vector prev(N,-1); vector v =find_winning(G,match,prev,i); for(int j =0; j < N; j++) if(v[j]) is_winning[j] =true;} for(int i =0; i < N; i++) if(is_winning[i]) ans++; cout << ans << "\n"; } return 0;} // look at my code // my code is amazing