#include <bits/stdc++.h>
#define L(i, m, n) for(int i(m);i < n;i++)
#define pb push_back
#define D(X) cout<<"  "<<#X": "<<X<<endl;
#define in(x) cin >> x
#define SZ(X) int(X.size())
#define clr(A, V) L(i, 0, sizeof(A)) A[i]=V
#define ff first
#define RF(X) freopen(X, "r", stdin)
#define WF(X) freopen(X, "w", stdout)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
typedef pair<int, string> pis;
typedef vector<string> vs;
typedef pair<pair<int, int>, pair<int, int > > piiii;
typedef vector<vi> vii;
const int maxn=202;
bool vis[maxn];
int F(int s,vii &adj,vi &color){
    queue<int>q;q.push(s);
    color[s]=0;
    bool IS=1;
    while(!q.empty()&&IS){
        int u=q.front();q.pop();
        L(j,0,SZ(adj[j])){
            int c=adj[u][s];
            if(color[c]==1e9){
                color[c]=1-color[u];
                q.push(c);
            }
            else if(color[u]==color[c]){IS=0;break;}
        }
    }
    if(!IS)return -1;
    int w=0,b=0;
    L(i,0,maxn)if(!color[i])b++;else if(color[i]==1)w++;
    return min(w,b);
}
int main(){
    int t,n,e,x,y;in(t);
    while(t--){
        int ans=0;
        in(n),in(e);
        vector<vector<int> > adj(maxn,vector<int>());
        for(int i = 0;i < e;i++){
            D(i);
            cin >> x >> y;
            adj[x].pb(y);
            adj[y].pb(x);
        }
        vi color(maxn,1e9);bool is=1;
        L(i,0,n){
            if(color[i]==1e9){
                int ret=F(i,adj,color);
                if(ret==-1){
                    printf("-1\n");
                    is=0;
                    break;

                }
                else ans+=ret;
            }


        }
        if(is)printf("%d\n",ans);
    }




    return 0;
}