/*#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
ifstream file("C:\\Users\\86180\\Desktop\\P4149_2.txt");
	file>>n>>m;*/
#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define N 200010
#define mod 1000000007
#define itn int
#define debug(x) cout << #x << " is " << x << endl;
#define FOR(i,n) for(ll i=1;i<=n;i++)
#define rep(i) for(int i=head[u];i;i=t[i].Next)
using namespace std;
int a,b,c,n,m,k=0,T,vis[N],x[N],dis[N],ans[N],head[N],maxx=-INF;
struct node{
	int u,v,Next;
}t[2*N];
void add(int u,int v){
	t[++k].v=v;
	t[k].Next=head[u];
	head[u]=k;
}
void bfs(){
	queue<int>q;
	q.push(1);
	dis[1]=0;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		rep(i){
			int v=t[i].v;
			if(dis[v]!=-1)continue;
			dis[v]=dis[u]+1;
			q.push(v); 
		} 
	} 
}
void dfs(int u){
	ans[u]=dis[u];vis[u]=1;
	rep(i){
		int v=t[i].v;
		
		if(dis[v]>dis[u]){if(vis[v]==0)dfs(v);
			ans[u]=min(ans[u],ans[v]); 
		}
		else ans[u]=min(ans[u],dis[v]); 
	}
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		FOR(i,n){
			head[i]=0;
			dis[i]=-1;ans[i]=INF,vis[i]=0;
		}
		k=0;
		FOR(i,m){
			scanf("%d%d",&a,&b);
			add(a,b);
		}
		bfs();
		dfs(1);
		FOR(i,n)cout<<ans[i]<<' ';
		cout<<endl;
	}
}
