#include <bits/stdc++.h>
using namespace std;
inline int gi() {
  char c = getchar();
  int x = 0;
  for (; c < '0' || c > '9'; c = getchar())
    ;
  for (; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - '0';
  return x;
}
const int N = 1e5 + 5;
vector<int> e[N];
int col[N], f[N], ban[N], n, m, cu, cv;
void dfs1(int u, int fa) {
  for (auto v : e[u])
    if (v != fa && ban[u] != v) {
      if (col[v]) {
        cu = u, cv = v, ban[u] = v, ban[v] = u;
        continue;
      }
      col[v] = -col[u], dfs1(v, u);
    }
}
void dfs2(int u, int fa) {
  f[u] = col[u];
  for (auto v : e[u])
    if (v != fa && ban[u] != v) dfs2(v, u), f[u] += f[v];
}
int main() {
  int T = gi();
  while (T--) {
    n = gi(), m = gi();
    for (int i = 1; i <= n; ++i) e[i].clear(), col[i] = f[i] = ban[i] = 0;
    for (int i = 1; i <= m; ++i) {
      int u = gi(), v = gi();
      e[u].push_back(v), e[v].push_back(u);
    }
    if (n & 1) {
      puts("-1");
      continue;
    }
    col[1] = 1, dfs1(1, 0), dfs2(1, 0);
    if (m == n - 1) {
      if (f[1]) {
        puts("-1");
        continue;
      }
      int ans = 0;
      for (int i = 1; i <= n; ++i) ans += abs(f[i]);
      printf("%d\n", ans);
    } else {
      if (f[1] & 1) {
        puts("-1");
        continue;
      }
      int ans = abs(f[1] >> 1);
      col[cu] -= (f[1] >> 1), col[cv] -= (f[1] >> 1);
      dfs2(1, 0);
      for (int i = 1; i <= n; ++i) ans += abs(f[i]);
      printf("%d\n", ans);
    }
  }
}
