#include <bits/stdc++.h>
using namespace std;
struct node {
  int y, next;
} a[200010];
int first[100010], len;
int fa[100010], d[100010];
int mark[100010], f[100010];
int X, Y;
int A[100010], al;
int B[100010], bl;
long long ans;
int cmp(const void *xx, const void *yy) {
  int x = *(int *)xx, y = *(int *)yy;
  return x - y;
}
void ins(int x, int y) {
  a[++len].y = y;
  a[len].next = first[x];
  first[x] = len;
}
void dfs(int x, int F, int K) {
  f[x] = -1;
  int k, y;
  for (k = first[x]; k; k = a[k].next) {
    y = a[k].y;
    if (k == (K ^ 1) || mark[y]) continue;
    dfs(y, x, k);
  }
  if (F) {
    ans += abs(f[x]);
    f[F] -= f[x];
  }
}
void DFS(int x, int F, int K) {
  fa[x] = F;
  d[x] = d[F] + 1;
  int k, y;
  for (k = first[x]; k; k = a[k].next) {
    y = a[k].y;
    if (k == (K ^ 1)) continue;
    if (d[y]) {
      if (d[y] < d[x]) X = x, Y = y;
      continue;
    }
    DFS(y, x, k);
  }
}
int main() {
  int T, n, m, x, y, i, j;
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; i++) first[i] = 0, mark[i] = 0, d[i] = 0;
    len = 1;
    for (i = 1; i <= m; i++) {
      scanf("%d%d", &x, &y);
      ins(x, y);
      ins(y, x);
    }
    if (m == n - 1) {
      ans = 0;
      dfs(1, 0, 0);
      if (f[1])
        printf("-1\n");
      else
        printf("%I64d\n", ans);
    } else {
      ans = 0;
      DFS(1, 0, 0);
      for (x = X; x != Y; x = fa[x]) mark[x] = 1;
      mark[Y] = 1;
      al = 0;
      for (x = X; x != Y; x = fa[x]) {
        dfs(x, 0, 0);
        A[++al] = f[x];
      }
      dfs(Y, 0, 0);
      A[++al] = f[Y];
      X = 1;
      Y = 0;
      for (i = 1; i <= al; i++) {
        X *= -1;
        Y = A[i] - Y;
      }
      if (X == 1) {
        if (Y)
          printf("-1\n");
        else {
          bl = al;
          X = 1;
          Y = 0;
          for (i = 1; i <= al; i++) {
            X *= -1;
            Y = A[i] - Y;
            if (X == 1)
              B[i] = Y;
            else
              B[i] = -Y;
          }
          qsort(B + 1, bl, sizeof(int), cmp);
          int mid = (1 + bl) >> 1;
          for (i = 1; i <= bl; i++) ans += abs(B[i] - B[mid]);
          printf("%I64d\n", ans);
        }
      } else {
        if (Y % 2 == 0) {
          Y /= 2;
          for (i = 1; i <= al; i++) {
            Y = A[i] - Y;
            ans += abs(Y);
          }
          printf("%I64d\n", ans);
        } else
          printf("-1\n");
      }
    }
  }
  return 0;
}
