#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
struct Edge {
  int nxt, v;
} e[(N << 1) + 3];
int fe[N + 3];
int fa[N + 3];
bool vis[N + 3];
int dep[N + 3];
int a[N + 3];
int s[N + 3];
vector<int> vec;
int n, m, en, au, av, sum;
long long ans;
int absl(int x) { return x < 0 ? -x : x; }
void addedge(int u, int v) {
  en++;
  e[en].v = v;
  e[en].nxt = fe[u];
  fe[u] = en;
}
void dfs(int u, int prv) {
  a[u] = dep[u] & 1 ? -1 : 1;
  sum += a[u];
  s[u] = a[u];
  vis[u] = true;
  for (int i = fe[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    if (v == prv) continue;
    if (vis[v]) {
      au = u, av = v;
    } else {
      dep[v] = dep[u] + 1;
      fa[v] = u;
      dfs(v, u);
      s[u] += s[v];
    }
  }
}
void dfs2(int u, int prv) {
  s[u] = a[u];
  vis[u] = true;
  for (int i = fe[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    if (v == prv) continue;
    if (vis[v]) {
      au = u, av = v;
    } else {
      dep[v] = dep[u] + 1;
      dfs2(v, u);
      s[u] += s[v];
    }
  }
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
      int u, v;
      scanf("%d%d", &u, &v);
      addedge(u, v);
      addedge(v, u);
    }
    sum = 0;
    dep[1] = 0;
    dfs(1, 0);
    if (m == n - 1) {
      if (sum) {
        puts("-1");
      } else {
        ans = 0ll;
        for (int i = 1; i <= n; i++) {
          ans += absl(s[i]);
        }
        printf("%lld\n", ans);
      }
    } else if (m == n) {
      if (dep[au] > dep[av]) swap(au, av);
      if ((dep[au] ^ dep[av]) & 1) {
        if (sum) {
          puts("-1");
        } else {
          vec.clear();
          int v = av;
          while (dep[v] > dep[au]) {
            vec.push_back(-s[v]);
            v = fa[v];
          }
          sort(vec.begin(), vec.end());
          int x = vec[vec.size() >> 1];
          a[au] -= x;
          a[av] += x;
          for (int i = 1; i <= n; i++) vis[i] = 0;
          dfs2(1, 0);
          ans = absl(x);
          for (int i = 1; i <= n; i++) {
            ans += absl(s[i]);
          }
          printf("%lld\n", ans);
        }
      } else {
        if (absl(sum) & 1) {
          puts("-1");
        } else {
          if (sum > 0) {
            for (int i = 1; i <= n; i++) s[i] = -s[i], a[i] = -a[i];
            sum = -sum;
          }
          int x = (-sum) >> 1;
          a[au] += x;
          a[av] += x;
          for (int i = 1; i <= n; i++) vis[i] = 0;
          dfs2(1, 0);
          ans = x;
          for (int i = 1; i <= n; i++) {
            ans += absl(s[i]);
          }
          printf("%lld\n", ans);
        }
      }
    }
    for (int i = 1; i <= n; i++) fe[i] = vis[i] = fa[i] = 0;
    for (int i = 1; i <= en; i++) e[i].v = e[i].nxt = 0;
    en = 0;
  }
  return 0;
}
