/*
    Task    : New Year Party
    Author  : Phumipat C. [MAGCARI]
    Language: C++
    Created : 10 October 2022 [18:37]
*/
#include<bits/stdc++.h>
using namespace std;
vector<int > g[410];
int mark[410],comp[410];
int cnt = 0;
void dfs(int i){
    comp[cnt]++;
    mark[i] = 1;
    for(auto x:g[i]){
        if(mark[x]) continue;
        dfs(x);
    }
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int q,n,m,u,v;
    cin >> q;
    while(q--){
        cin >> n >> m;
        while(m--){
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        memset(mark,0,sizeof mark);
        memset(comp,0,sizeof comp);
        int mx = 0,mn = 1e9;
        cnt = 0;
        for(int i=1;i<=n;i++){
            if(mark[i]) continue;
            cnt++;
            dfs(i);
            mx = max(mx,comp[cnt]);
            mn = min(mn,comp[cnt]);
            // printf("cnt mx mn: %d %d %d\n",cnt,mx,mn);
        }
        if(cnt > 2)
            cout << "-1\n";
        else if(cnt == 2)
            cout << mx - mn << '\n';
        else
            cout << mx%2 << '\n';
        for(int i=1;i<=n;i++)
            g[i].clear();
    }
    return 0;
}