#include <bits/stdc++.h>
#define ll long long int
using namespace std;

ll mod = 998244353;
const int maxn = 1000010;

void calc_primes();
void calc_fact();
ll bin_pow(ll,ll);
ll C(ll,ll);
vector<bool> primes(maxn,false);
ll fact[maxn];

const int siz = 3e5+10;
vector<ll> adj[siz];
vector<ll> visited(siz);
vector<ll> color(siz);
ll cnt=0,color_count=0;

vector<ll> bfs(vector<vector<ll>> &adj,ll n){
	vector<ll> dist(n,-1);
	dist[0]=0;
	queue<ll> q;
	q.push(0);
	while(q.size()){
		ll u = q.front();
		q.pop();
		for(auto x:adj[u]){
			if(dist[x]==-1){
				dist[x]= dist[u]+1;
				q.push(x);
			}
		}
	}
	return dist;
}


void solve(){
	ll temp=0,flag=1;
	
	ll n,m; cin>>n>>m;
	vector<vector<ll>> adj(n);
	vector<bool> visited(n,false);
	for(ll i=0;i<m;i++){
		ll a,b; cin>>a>>b; a--,b--;
		adj[a].push_back(b);
	}
	vector<ll> dist = bfs(adj,n);
	vector<pair<ll,ll>> dist_sorted(n);

	for(ll i=0;i<n;i++) dist_sorted[i]={dist[i],i};
	sort(dist_sorted.begin(),dist_sorted.end());
	reverse(dist_sorted.begin(),dist_sorted.end());

	vector<ll> ans(n);
	for(auto p:dist_sorted){
		ll u = p.second;
		ans[u] = p.first;
		for(auto x:adj[u]){
			if(dist[x]<=dist[u]){
				ans[u] = min(ans[u],dist[x]);
			}
			else ans[u] = min(ans[u],ans[x]);
		}
	}
	for(auto x:ans){
		cout << x<<" ";
	}
	cout <<"\n";
}

int main(){
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int  t=1;cin>>t;while(t--) 
	solve();
	return 0;
}


//calculate primes
void calc_primes(){
	for(ll i=2;i<maxn;i++){
		if(!primes[i]){
			for(ll j=2*i;j<maxn;j+=i){
				primes[j]=true;
			}
		}
	}
}
// calculate factorial
void calc_fact(){
	fact[0]=1;
	for(ll i=1;i<maxn;i++){
		fact[i] = (fact[i-1]*i)%mod;
	}
}
// calculate a^b in log(b) time 
ll bin_pow(ll x,ll y){
	ll res=1;
	while(y){
		if(y%2)res=(res*x)%mod;
		x=(x*x)%mod;
		y/=2;
	}
	return res;
}
// calculate nCr%mod
ll C(ll n,ll r){
	if(r>n)return 0;
	ll a=fact[r];
	a=(a*fact[n-r])%mod;
	ll b=fact[n];
	a=bin_pow(a,mod-2);
	b=(a*b)%mod;
	return b;
}
//priority_queue,push_back,pop_back