la4186.cc

#include <cstring>
#include <vector>
#include <cassert>
#include <cstdio>
#include <iostream>

using namespace std;

#define MAXN 100000

typedef std::pair<int, int> pii;

int N, sz; //nodes
pii S[MAXN], E[MAXN];
int cnt = 0, V[MAXN<<1], vsz, esz, B[MAXN], bsz;

inline void outComp(const pii &tt) {
  B[bsz++] = esz;
  do {
     E[esz].first = S[--sz].first;
     E[esz++].second = S[sz].second;
  } while (S[sz] != tt);
}

std::vector<int> ady[MAXN];
int low[MAXN] , num[MAXN], parent[MAXN], dfsnumbercounter;
void arpts(int u) {
  low[u] = num[u] = ++dfsnumbercounter;
  int v;
  for (int i = 0; i < ady[u].size(); ++ i) {
    v = ady[ u ][ i ] ;
    if( num [ v ] == -1 ){
      S[sz].first = u; S[sz++].second = v;
      parent[v] = u;
      arpts(v);
      if( low[ v ] >= num[ u ] )
        outComp(pii(u, v));
      low[u] = std::min( low[ u ] , low [ v ]);
    }
    else if( v != parent[u] and num[v] < num[u]) {
      S[sz].first = u; S[sz++].second = v;
      low[ u ] = std::min( low[ u ] , num [ v ]);
    }
  }
}

inline void calc(){
  dfsnumbercounter = sz = 0;
  memset(num, -1, sizeof num);
  for (int i = 0 ; i < N  ; ++i)
    if (num[i] == -1)
      arpts(i);
}

int col[MAXN];
bool lucky[MAXN];

int tc, m, u, v, ans;
int main() {
  scanf("%d", &tc);
  while (tc--) {
    scanf("%d %d", &N, &m);
    for (u = 0; u < N; ++u)
      vector<int>().swap(ady[u]);
    while (m--) {
      scanf("%d %d", &u, &v);
      --u; --v;
      ady[u].push_back(v);
      ady[v].push_back(u);
    }
    memset(lucky, false, sizeof lucky);
    memset(col, 0, sizeof col);
    bsz = esz = 0;
    calc();
    cnt = 0;
    --esz;
    bool valid;
    while (bsz--) {
      ++cnt;
      vsz = 0;
      valid = true;
      for ( ; esz >= B[bsz]; --esz) {
        int &cu = col[V[vsz++] = E[esz].first],
            &cv = col[V[vsz++] = E[esz].second];
        if ((cu >> 1) == cnt) {
          if ((cv >> 1) == cnt)
            valid &= cu != cv;
          else
            cv = cu ^ 1;
        } else {
          if ((cv >> 1) != cnt)
            cv = cnt << 1;
          cu = cv ^ 1;
        }
      }
      //cout << valid << endl;
      if (not valid) {
        while (vsz--)
          lucky[V[vsz]] = true;
      }
    }
    ans = 0;
    for (u = 0; u < N; ++u)
      if (lucky[u])
        ++ans;
    printf("%d\n", ans);
  }
}