#include <bits/stdc++.h>
using namespace std;
const int INF = 1000010;
int mymin(int x, int y) { return x < y ? x : y; }
struct node {
  int x, y, next;
} t[100010 * 2];
int len, first[100010];
void ins(int x, int y) {
  t[++len].x = x;
  t[len].y = y;
  t[len].next = first[x];
  first[x] = len;
}
int r1, r2, ad;
int sm[100010], ss[100010], ans, d[100010], h[100010];
int dfs(int x, int fa, int dep) {
  sm[x] = 1;
  ss[x] = dep;
  d[x] = dep;
  if (x == r1 || x == r2) sm[x] += ad, ss[x] += ad;
  int tt = 0;
  for (int i = first[x]; i; i = t[i].next)
    if (t[i].y != fa) {
      int y = t[i].y;
      tt += dfs(y, x, 1 - dep);
      sm[x] += sm[y];
      ss[x] += ss[y];
    }
  if (x == r1) tt++;
  if (x == r2) tt--;
  if (tt == -1)
    h[++h[0]] = ss[x] - (sm[x] - ss[x]);
  else if (tt == 1)
    h[++h[0]] = (sm[x] - ss[x]) - ss[x];
  else
    ans += abs(ss[x] - (sm[x] - ss[x]));
  return tt;
}
int ff[100010];
int ffa(int x) {
  if (ff[x] != x) ff[x] = ffa(ff[x]);
  return ff[x];
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int n, m;
    r1 = r2 = 0;
    scanf("%d%d", &n, &m);
    len = 0;
    memset(first, 0, sizeof(first));
    for (int i = 1; i <= n; i++) ff[i] = i;
    for (int i = 1; i <= m; i++) {
      int x, y;
      scanf("%d%d", &x, &y);
      if (ffa(x) != ffa(y)) {
        ff[ffa(x)] = ffa(y);
        ins(x, y);
        ins(y, x);
      } else
        r1 = x, r2 = y;
    }
    if (m == n - 1) {
      dfs(1, 0, 0);
      ans = 0;
      for (int i = 1; i <= n; i++) ans += abs(ss[i] - (sm[i] - ss[i]));
      if (sm[1] - ss[1] != ss[1])
        printf("-1\n");
      else
        printf("%d\n", ans);
    } else {
      ad = 0;
      dfs(1, 0, 0);
      if (d[r1] == d[r2]) {
        ad = abs(ss[1] - (sm[1] - ss[1]));
        if (ad & 1)
          printf("-1\n");
        else {
          ad /= 2;
          if (ss[1] > sm[1] - ss[1])
            dfs(1, 0, 1);
          else
            dfs(1, 0, 0);
          ans = ad;
          for (int i = 1; i <= n; i++) ans += abs(ss[i] - (sm[i] - ss[i]));
          printf("%d\n", ans);
        }
      } else {
        h[0] = 0;
        h[++h[0]] = 0;
        ans = 0;
        dfs(1, 0, 0);
        if (sm[1] - ss[1] != ss[1])
          printf("-1\n");
        else {
          sort(h + 1, h + 1 + h[0]);
          int x = h[h[0] / 2 + 1];
          for (int i = 1; i <= h[0]; i++) ans += abs(h[i] - x);
          printf("%d\n", ans);
        }
      }
    }
  }
  return 0;
}
