#include<bits/stdc++.h>
#define N 1000010 
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const double eps=1e-6;
struct node{
	int per,to,w;
}e[N];
struct Node{
	int cur,d;
	bool operator<(const Node &tmp)const{
		return d>tmp.d;
	}
};
int head[N],ans[N],dis[N];
bool vis[N];
int t,n,m,tot;
void addedge(int from,int to)
{
	e[++tot].to=to;
	e[tot].per=head[from];
	e[tot].w=1;
	head[from]=tot;
}
void init()
{
	tot=0;
	for(int i=1;i<=n;++i)
	{
		head[i]=-1;
		dis[i]=inf;
		ans[i]=inf;
		vis[i]=0;
	}
}
void dji()
{
	priority_queue<Node> que;
	que.push({1,0});
	dis[1]=0;
	while(!que.empty())
	{
		Node cur=que.top();
		que.pop();
		int u=cur.cur,dist=cur.d;
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];i>0;i=e[i].per)
		{
			int v=e[i].to;
			if(dis[u]+e[i].w<dis[v]){
				dis[v]=dis[u]+e[i].w;
				que.push({v,dis[v]});
			}
		}
	}
}
int dfs(int u,int fa)
{
	vis[u]=1;
	int res=ans[u];
	for(int i=head[u];i>0;i=e[i].per)
	{
		int v=e[i].to;
		if(v==fa||dis[v]<=dis[u]) continue;
		if(vis[v]){
			res=min(res,ans[v]);
		}
		else res=min(res,dfs(v,u));
	}
	ans[u]=min(ans[u],res);
	return ans[u];
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		init();
		for(int i=1;i<=m;++i)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			addedge(x,y);
		}
		dji();
		for(int i=1;i<=n;++i)
		{
			ans[i]=dis[i];
			vis[i]=0;
		}
		for(int i=1;i<=n;++i)
		{
			for(int j=head[i];j>0;j=e[j].per)
			{
				int v=e[j].to;
				ans[i]=min(ans[i],dis[v]);
			}
		}
		dfs(1,-1);
		for(int i=1;i<=n;++i)
		{
			printf("%d ",ans[i]);
		}
	}
	return 0;
}