#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 100100
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
using namespace std;
vector<int>edge[MAXN];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(ch>'9'||ch<'0')  {if(ch=='-')  f=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9')  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
int getlen(int l,int r){
	if(!edge[l].size())  return -1;
	if(edge[l].size()==1) return edge[l][0]-l;
	int mid=(l+r+1)>>1;
	if(edge[l][edge[l].size()-1]==mid) return mid-l;
	else return edge[l][edge[l].size()-1]-edge[l][edge[l].size()-2];
}
int solve(int l,int r){
	if(l==r) return 0;
	int len=getlen(l,r); if(len<=0) return -1;
	for(int i=l;i<=l+len-1;++i){
		for(int j=(r-i)/len*len+i;j>=l+len;j-=len){
			if(edge[i].size()&&edge[i].back()==j) edge[i].erase(edge[i].end()-1);
			else return -1;
		}
	}
	int Lans=solve(l,l+len-1);
	int Rans=solve(l+len,r);
	if(Lans==-1||Rans==-1) return -1;
	else return max(Lans,Rans)+1;
}
void solve(){
	int n=read(),m=read();
	for(int i=0;i<n;++i) edge[i].clear();
	for(int i=1;i<=m;++i){
		int x=read(),y=read();
		if(x>y)  swap(x,y);
		edge[x].push_back(y);
	}
	for(int i=0;i<n;++i) sort(edge[i].begin(),edge[i].end(),less<int>());
	int ans=solve(0,n-1);
	for(int i=0;i<n;++i)if(edge[i].size()){puts("-1");return;}
	printf("%d\n",ans);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	for(int T=read();T;--T) solve();
	return 0;
}