#include<bits/stdc++.h>
using namespace std;
#define int long long
const int Maxn=2e5+7;
const int INF=0x3f3f3f3f;

int T,n,m;
int ans[Maxn],dis[Maxn],vis[Maxn];
vector<int> ve[Maxn];
queue<int> q;

void dfs(int u)
{
	vis[u]=1;
	ans[u]=dis[u];
	for(int i=0;i<ve[u].size();i++)
	{
		int v=ve[u][i];
		if(dis[v]>dis[u]&&!vis[v])
		{
			dfs(v);
		}
		if(dis[v]>dis[u])
		{
			ans[u]=min(ans[u],ans[v]);
		}
		else ans[u]=min(ans[u],dis[v]);
	}
}

signed main()
{
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
			dis[i]=ans[i]=INF;
			ve[i].clear();
			vis[i]=0;
		}
		while(m--)
		{
			int u,v;
			cin>>u>>v;
			ve[u].push_back(v);
		}
		dis[1]=0;ans[1]=0;
		q.push(1);
		while(q.size())
		{
			int head=q.front();
			q.pop();
			for(int i=0;i<ve[head].size();i++)
			{
				int tmp=ve[head][i];
				if(dis[tmp]==INF)
				{
					dis[tmp]=dis[head]+1;
					q.push(tmp); 
				}
			}
		}
		dfs(1);
		
		for(int i=1;i<=n;i++)
			cout<<ans[i]<<' ';
		cout<<'\n';
	}
	return 0; 
}
