#include <bits/stdc++.h>
namespace io {
int F() {
  int n = 0, F = 1;
  char ch;
  while ((ch = getchar()) != '-' && (ch < '0' || ch > '9'))
    ;
  ch == '-' ? F = 0 : n = ch - '0';
  while ((ch = getchar()) >= '0' && ch <= '9') n = n * 10 + ch - '0';
  return F ? n : -n;
}
}  // namespace io
struct edge {
  int to;
  int next;
} e[333333];
int pe = 111111;
int deg[111111];
void insert(int a, int to) {
  e[pe] = (edge){to, e[a].next};
  e[a].next = pe++;
  ++deg[to];
}
int siz[111111][2];
int c[111111];
int q[111111], hq, tq;
int cyc[111111];
long long ans;
void dfs(int o, int fa) {
  siz[o][c[o]] = 1, siz[o][!c[o]] = 0;
  for (register int p = e[o].next; p; p = e[p].next)
    if (e[p].to != fa) {
      c[e[p].to] = !c[o];
      dfs(e[p].to, o);
      siz[o][0] += siz[e[p].to][0];
      siz[o][1] += siz[e[p].to][1];
    }
  int d = ((siz[o][0]) < (siz[o][1]) ? (siz[o][0]) : (siz[o][1]));
  siz[o][0] -= d, siz[o][1] -= d;
  ans += siz[o][0] + siz[o][1];
}
int pv, cnt[222222][2], d[222222], v[111111];
void dfs2(int o, int fa) {
  siz[o][0] = 1;
  siz[o][1] = 0;
  for (register int p = e[o].next; p; p = e[p].next)
    if (e[p].to != fa && !cyc[e[p].to]) {
      dfs2(e[p].to, o);
      siz[o][0] += siz[e[p].to][1];
      siz[o][1] += siz[e[p].to][0];
    }
  int d = ((siz[o][0]) < (siz[o][1]) ? (siz[o][0]) : (siz[o][1]));
  siz[o][0] -= d, siz[o][1] -= d;
  ans += siz[o][0] + siz[o][1];
}
void dfs3(int o, int fa, int top) {
  dfs2(o, o);
  ++pv;
  cnt[pv][0] = siz[o][0];
  cnt[pv][1] = siz[o][1];
  ans -= siz[o][0] + siz[o][1];
  for (register int p = e[o].next; p; p = e[p].next)
    if (e[p].to != fa && e[p].to != top && cyc[e[p].to]) {
      dfs3(e[p].to, o, top);
      return;
    }
}
int main() {
  freopen("reverse.in", "r", stdin);
  freopen("reverse.out", "w", stdout);
  int T = io::F();
  while (T--) {
    pe = 111111;
    for (register int i = 1; i <= pe; ++i) e[i].next = 0;
    memset(deg, 0, sizeof(deg));
    int n = io::F(), m = io::F();
    for (register int i = 1; i <= m; ++i) {
      int x = io::F(), y = io::F();
      insert(x, y);
      insert(y, x);
    }
    if (n & 1) {
      puts("-1");
      continue;
    }
    if (m == n - 1) {
      ans = 0;
      dfs(1, 1);
      if (siz[1][0] || siz[1][1]) {
        puts("-1");
        continue;
      }
      printf("%lld\n", ans);
      continue;
    } else {
      int md = 0;
      for (register int i = 1; i <= n; ++i)
        (md < (deg[i]) ? md = (deg[i]), 1 : 0);
      if (md == 2) {
        printf("%d\n", n / 2);
        continue;
      }
      hq = tq = 1;
      for (register int i = 1; i <= n; ++i)
        if (deg[i] == 1)
          q[tq++] = i, cyc[i] = 0;
        else
          cyc[i] = 1;
      for (; hq != tq; ++hq)
        for (register int p = e[q[hq]].next; p; p = e[p].next)
          if (--deg[e[p].to] == 1) q[tq++] = e[p].to, cyc[e[p].to] = 0;
      ans = 0;
      pv = 0;
      for (register int i = 1; i <= n; ++i)
        if (cyc[i]) {
          dfs3(i, i, i);
          break;
        }
      for (register int i = 1; i <= pv; ++i) d[i] = cnt[i][0] - cnt[i][1];
      if (pv & 1) {
        int sum = 0;
        for (register int i = 1; i <= pv; ++i)
          if (i & 1)
            sum -= d[i];
          else
            sum += d[i];
        sum /= 2;
        d[1] += sum, d[pv] += sum;
        ans += ((sum) > 0 ? (sum) : -(sum));
        for (register int i = 1; i < pv; ++i)
          d[i + 1] -= d[i], ans += ((d[i]) > 0 ? (d[i]) : -(d[i]));
      } else {
        int so = 0, se = 0;
        for (register int i = 1; i <= pv; ++i)
          if (i & 1)
            so += d[i];
          else
            se += d[i];
        if (so != se) {
          puts("-1");
          continue;
        }
        v[pv] = 0;
        for (register int i = 1; i < pv; ++i) {
          if (i & 1)
            v[i] = d[i];
          else
            v[i] = -d[i];
          d[i + 1] -= d[i];
        }
        std::nth_element(v + 1, v + pv / 2, v + pv + 1);
        int x = v[pv / 2];
        for (register int i = 1; i <= pv / 2; ++i) ans += x - v[i];
        for (register int i = pv / 2 + 1; i <= pv; ++i) ans += v[i] - x;
      }
      printf("%lld\n", ans);
    }
  }
  return 0;
}
