#include <bits/stdc++.h>
using namespace std;
const int Maxn = 1e5 + 10;
struct EDGE {
  int x, y, next;
} edge[Maxn * 2];
int len, first[Maxn];
void ins(int x, int y) {
  len++;
  edge[len].x = x;
  edge[len].y = y;
  edge[len].next = first[x];
  first[x] = len;
}
int N, M;
int C[Maxn];
int u, v, opt;
bool vis[Maxn];
void Find_Cir(int x, int fa, int col) {
  C[x] = col;
  vis[x] = 1;
  for (int k = first[x]; k != -1; k = edge[k].next) {
    int y = edge[k].y;
    if (x == u && y == v) continue;
    if (y != fa) {
      if (vis[y]) {
        u = x;
        v = y;
        if (C[u] == C[v])
          opt = 1;
        else
          opt = 0;
      } else
        Find_Cir(y, x, -col);
    }
  }
}
int G[Maxn], F[Maxn];
void Dfs(int x, int fa) {
  F[x] = C[x];
  for (int k = first[x]; k != -1; k = edge[k].next) {
    int y = edge[k].y;
    if (x == u && y == v) continue;
    if (x == v && y == u) continue;
    if (y != fa) {
      Dfs(y, x);
      F[x] += F[y];
      G[x] += G[y];
    }
  }
}
int A[Maxn];
int Alen;
int main() {
  int Tcase;
  scanf("%d", &Tcase);
  while (Tcase--) {
    scanf("%d%d", &N, &M);
    len = 0;
    memset(first, -1, sizeof(first));
    for (int i = 1; i <= M; i++) {
      int x, y;
      scanf("%d%d", &x, &y);
      ins(x, y);
      ins(y, x);
    }
    memset(vis, 0, sizeof(vis));
    memset(C, 0, sizeof(C));
    u = v = 0;
    Find_Cir(1, 0, 1);
    if (M == N - 1) {
      Dfs(1, 0);
      if (F[1])
        printf("-1\n");
      else {
        int ans = 0;
        for (int i = 1; i <= N; i++) ans += abs(F[i]);
        printf("%d\n", ans);
      }
    } else if (opt == 1) {
      Dfs(1, 0);
      int t = F[1], ans = 0;
      if (t & 1)
        printf("-1\n");
      else {
        C[u] -= t / 2;
        C[v] -= t / 2;
        ans += abs(t / 2);
        memset(F, 0, sizeof F);
        Dfs(1, 0);
        for (int i = 1; i <= N; i++) ans += abs(F[i]);
        printf("%d\n", ans);
      }
    } else if (opt == 0) {
      Dfs(1, 0);
      if (F[1])
        printf("-1\n");
      else {
        memset(G, 0, sizeof(G));
        G[u]--;
        G[v]++;
        memset(F, 0, sizeof F);
        Dfs(1, 0);
        int ans = 0;
        Alen = 0;
        memset(A, 0, sizeof(A));
        for (int i = 1; i <= N; i++) {
          if (G[i] == -1) A[++Alen] = F[i];
          if (G[i] == 0) ans += abs(F[i]);
          if (G[i] == 1) A[++Alen] = -F[i];
        }
        sort(A + 1, A + Alen + 1);
        for (int i = 1; i <= Alen; i++) ans += abs(A[i] - A[(Alen + 1) >> 1]);
        ans += abs(A[(Alen + 1) >> 1]);
        printf("%d\n", ans);
      }
    }
  }
  return 0;
}
