#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#define N 200000
#define inf 1e9
using namespace std;
int read()
{
    char c=0;
    int sum=0;
    while (c<'0'||c>'9') c=getchar();
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}
void Adder(int &x,int d)
{
    x=(x<d)?x:d;
    return;
}
struct reads
{
    int num,data;
};
int T,n,m,ans,q[N+1],dis[N+1],dis2[N+1];
bool used[N+1];
vector<int>E[N+1];
vector<reads>p[N+1];
vector<vector<int>>dp[N+1];
void add(int x,int y)
{
    E[x].push_back(y),E[y].push_back(x);
    return;
}
void bfs()
{
    queue<int>q;
    int top;
    q.push(1),dis[1]=0;
    while (!q.empty())
    {
	top=q.front(),q.pop();
	for (int i=0;i<E[top].size();++i)
	    if (dis[E[top][i]]>dis[top]+1)
		dis[E[top][i]]=dis[top]+1,q.push(E[top][i]);
    }
    return;
}
void bfs2()
{
    queue<int>q;
    int top;
    for (int i=1;i<=n;++i)
	if (used[i])
	    q.push(i),dis2[i]=dis[i];
    while (!q.empty())
    {
	top=q.front(),q.pop();
	for (int i=0;i<E[top].size();++i)
	    if (dis2[E[top][i]]>dis2[top]+1)
		dis2[E[top][i]]=dis2[top]+1,q.push(E[top][i]);
    }
    return;
}
bool cmp(int x,int y)
{
    return dis[x]<dis[y];
}
int main()
{
    bool op;
    int x,y,ps,res,minn;
    T=read();
    while (T--)
    {
	n=read(),m=read(),ans=0,op=1;
	for (int i=0;i<=(n<<1);++i) p[i].clear(),dp[i].clear();
	for (int i=1;i<=n;++i) E[i].clear(),used[i]=0,dis[i]=dis2[i]=inf;
	for (int i=1;i<=m;++i) x=read(),y=read(),add(x,y);
	bfs();
	for (int i=1;i<=n;++i)
	    for (int j=0;j<E[i].size();++j)
		if (dis[i]==dis[E[i][j]])
		    used[i]=1;
	for (int i=1;i<=n;++i) op&=(!used[i]);
	if (op)
	{
	    printf("%d\n",n-1);
	    continue;
	}
	bfs2();
	for (int i=1;i<=n;++i) q[i]=i;
	sort(q+1,q+n+1,cmp);
	for (int i=1;i<=n;++i)
	{
	    if (!p[dis[q[i]]+dis2[q[i]]].empty()&&p[dis[q[i]]+dis2[q[i]]].back().num==dis[q[i]]) p[dis[q[i]]+dis2[q[i]]].back().data++;
	    else p[dis[q[i]]+dis2[q[i]]].push_back((reads){dis[q[i]],1});
	}
	for (int i=0;i<=(n<<1);++i)
	    if (!p[i].empty())
	    {
		dp[i].resize(p[i].size()+1),ps=-1,minn=inf;
		for (int j=0;j<p[i].size();++j)
		{
		    while (i>=2&&ps+1<p[i-2].size()&&p[i-2][ps+1].num<=p[i][j].num-1) ps++;
		    op=(ps!=-1&&p[i-2][ps].num==p[i][j].num-1),dp[i][j].resize(p[i][j].data+1);
		    for (int k=0;k<dp[i][j].size();++k) dp[i][j][k]=inf;
		    if (!j||p[i][j-1].num+1!=p[i][j].num)
		    {
			if (j)
			{
			    res=inf;
			    for (int k=0;k<dp[i][j-1].size();++k) Adder(res,dp[i][j-1][k]);
			}
			else res=0;
			if (!p[i][j].num)
			{
			    if (!op)
			    {
				dp[i][j][p[i][j].data]=res;
			    }
			    else
			    {
				for (int k=0;k<dp[i][j].size();++k) dp[i][j][k]=res+p[i][j].data-k;
			    }
			}
			else if (op) dp[i][j][0]=res+p[i][j].data;
		    }
		    else
		    {
			if (!op)
			{
			    for (int k=0;k<dp[i][j-1].size();++k) Adder(dp[i][j][p[i][j].data],dp[i][j-1][k]+max(k,p[i][j].data));
			}
			else
			{
			    res=inf;
			    for (int k=0;k<dp[i][j].size();++k)
			    {
				if (k<dp[i][j-1].size()) Adder(res,dp[i][j-1][k]);
				Adder(dp[i][j][k],res+p[i][j].data);
			    }
			    res=inf;
			    for (int k=dp[i][j].size();k<dp[i][j-1].size();++k) Adder(res,dp[i][j-1][k]+k);
			    for (int k=(int)(dp[i][j].size())-1;k>=0;--k)
			    {
				Adder(dp[i][j][k],res+p[i][j].data-k);
				if (k<dp[i][j-1].size()) Adder(res,dp[i][j-1][k]+k);
			    }
			}
		    }
		}
		if ((p[i].back().num<<1)==i)
		{
		    for (int j=0;j<dp[i][(int)(p[i].size())-1].size();++j) Adder(minn,dp[i][(int)(p[i].size())-1][j]+((j+1)>>1));
		}
		else Adder(minn,dp[i][(int)(p[i].size())-1][0]);
		ans+=minn;
	    }
	printf("%d\n",ans);
    }
    return 0;
}