#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;

const int maxn = 1E5 + 10;

struct E{
	int x,y; E(){}
	E(int x,int y): x(x),y(y){}
}edgs[maxn];

int n,m,Black,White,Ans,A,B,tp,f[maxn],fa[maxn],L[maxn],stk[maxn];
bool flag;

vector <int> v[maxn];

int getint()
{
	char ch = getchar(); int ret = 0;
	while (ch < '0' || '9' < ch) ch = getchar();
	while ('0' <= ch && ch <= '9')
		ret = ret * 10 + ch - '0',ch = getchar();
	return ret;
}

void Color(int x,int from)
{
	int now = f[x];
	if (now == 1) ++Black; else ++White;
	for (int i = 0; i < v[x].size(); i++)
	{
		int to = v[x][i];
		if (to == from) continue;
		if (L[to])
		{
			if (L[to] > L[x]) continue;
			flag = (L[x] - L[to] & 1) ? 0 : 1;
			A = to; B = x; continue;
		}
		f[to] = -now; L[to] = L[x] + 1;
		Color(to,x); fa[to] = x; f[x] += f[to];
	}
}

void Add(int x,int delta)
{
	for (int i = x; i; i = fa[i])
		f[i] += delta;
}

void Calc_Ans()
{
	for (int i = 1; i <= m; i++)
	{
		if (edgs[i].x == A && edgs[i].y == B) continue;
		if (edgs[i].x == B && edgs[i].y == A) continue;
		Ans += abs(f[L[edgs[i].x] > L[edgs[i].y] ? edgs[i].x : edgs[i].y]);
	}
	printf("%d\n",Ans);
}

void Check1()
{
	if (Black != White) {puts("-1"); return;}
	Calc_Ans();
}

void Check2()
{
	if (Black != White)
	{
		if (abs(Black - White) % 2 != 0) {puts("-1"); return;}
		int delta = (Black - White) / -2;
		Ans = abs(delta); Add(A,delta); Add(B,delta);
	}
	Calc_Ans();
}

void Check3()
{
	if (Black != White) {puts("-1"); return;}
	for (int i = B; i != A; i = fa[i]) stk[++tp] = f[i];
	sort(stk + 1,stk + tp + 1);
	int tmp = stk[(tp + 1) / 2]; Add(A,tmp); Add(B,-tmp);
	Ans = abs(tmp); Calc_Ans();
}

void Solve()
{
	n = getint(); m = getint();
	for (int i = 1; i <= m; i++)
	{
		int x = getint(),y = getint();
		edgs[i] = E(x,y); v[x].push_back(y); v[y].push_back(x);
	}
	f[1] = L[1] = 1; Color(1,0);
	if (m == n - 1) Check1();
	else if (flag) Check2(); else Check3();
}

void Clear()
{
	Ans = flag = Black = White = tp = 0;
	for (int i = 1; i <= n; i++) v[i].clear(),L[i] = 0;
}

int main()
{
	
	int T = getint();
	while (T--) Solve(),Clear();
	return 0;
}