#include <bits/stdc++.h>
using namespace std;
const int N = 100005, E = 262144;
const int M = 998244353;
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c,
                                       qu[55];
int f, qr;
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
}
inline void putc(char x) {
  *oS++ = x;
  if (oS == oT) flush();
}
template <class I>
inline void gi(I &x) {
  for (f = 1, c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                            : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == '-') f = -1;
  for (x = 0; c <= '9' && c >= '0';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    x = x * 10 + (c & 15);
  x *= f;
}
template <class I>
inline void print(I x) {
  if (!x) putc('0');
  if (x < 0) putc('-'), x = -x;
  while (x) qu[++qr] = x % 10 + '0', x /= 10;
  while (qr) putc(qu[qr--]);
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io ::gi;
using io ::print;
using io ::putc;
int n, m, i, head[N], Next[N * 2], adj[N * 2], c[N], k, siz[N], u[N], v[N],
    f[N];
int sta[N], top, insta[N], cy[N], p;
long long ans;
int Find(int x) { return f[x] ? f[x] = Find(f[x]) : x; }
void uniot(int u, int v) {
  int x = Find(u), y = Find(v);
  if (x != y) f[x] = y;
}
void Push(int u, int v) {
  Next[++k] = head[u];
  head[u] = k;
  adj[k] = v;
}
void dfs(int i, int f) {
  int j;
  if (c[i])
    ++siz[i];
  else
    --siz[i];
  for (j = head[i]; j; j = Next[j])
    if (adj[j] != f) {
      c[adj[j]] = c[i] ^ 1;
      dfs(adj[j], i);
      siz[i] += siz[adj[j]];
    }
  if (f) ans += abs(siz[i]);
}
void dfs2(int i, int f) {
  int j, k;
  sta[++top] = i;
  insta[i] = top;
  for (j = head[i]; j; j = Next[j])
    if (adj[j] != f) {
      if (insta[adj[j]]) {
        for (k = insta[adj[j]]; k <= top; ++k) cy[p++] = sta[k];
        return;
      }
      dfs2(adj[j], i);
    }
  insta[sta[top]] = 0;
  --top;
}
int main() {
  int _;
  gi(_);
  while (_--) {
    gi(n), gi(m);
    memset(head, 0, sizeof(head));
    memset(siz, 0, sizeof(siz));
    ans = k = 0;
    for (i = 1; i <= m; ++i) {
      gi(u[i]), gi(v[i]);
      Push(u[i], v[i]);
      Push(v[i], u[i]);
    }
    if (m == n - 1) {
      ans = 0;
      dfs(1, 0);
      if (siz[1] != 0) ans = -1;
      cout << ans << endl;
    }
    if (m == n) {
      p = top = 0;
      dfs2(1, 0);
      if (p & 1) {
        k = 0;
        memset(head, 0, sizeof(head));
        memset(f, 0, sizeof(f));
        int au, av;
        for (i = 1; i <= m; ++i)
          if (Find(u[i]) != Find(v[i])) {
            uniot(u[i], v[i]);
            Push(u[i], v[i]);
            Push(v[i], u[i]);
          } else
            au = u[i], av = v[i];
        dfs(1, 0);
        if (abs(siz[1]) & 1)
          puts("-1");
        else {
          int tmp = siz[1] / 2;
          memset(siz, 0, sizeof(siz));
          siz[au] = siz[av] = -tmp;
          ans = 0;
          dfs(1, 0);
          cout << ans + abs(tmp) << endl;
        }
      } else {
        int p[1000];
        cout << p[1000000];
        cout << 0 / 0;
      }
    }
  }
}
