#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
using namespace std;
int dis[200005],dp[200005];
bool f[200005];
vector <int> v[200005];
queue <int> q;
void Dfs(int x,int p){
    f[x] = 1;
    for (int j=0;j<v[x].size();j++){
        int to = v[x][j];
        if (dis[x] >= dis[to]) continue;
        if (!f[to]) Dfs(to,x);
        dp[x] = min(dp[x],dp[to]);
    }
}
int main (){
    int t;
    cin>>t;
    for (int i=1;i<=200000;i++) dp[i] = dis[i] = 1e9;
    
    while(t--){
        int n,m;
        cin>>n>>m;
        for (int i=1;i<=m;i++){
            int a,b;
            cin>>a>>b;
            v[a].pb(b);
        }
        dis[1] = dp[1] = 0; f[1] = 1;
        q.push(1);
        while(q.size()){
            int x = q.front();
            q.pop();
            for (int j=0;j<v[x].size();j++){
                int to = v[x][j];
                if (!f[to]){
                    f[to] = 1;
                    dis[to] = dis[x] + 1;
                    q.push(to);
                }
            }
        }
        
        for (int i=2;i<=n;i++){
            dp[i] = dis[i];
            for (int j=0;j<v[i].size();j++)
                dp[i] = min(dp[i],dis[v[i][j]]);
        }
        for (int i=1;i<=n;i++) f[i]=0;
        Dfs(1,1);
        
        for (int i=1;i<=n;i++) {
            cout<<dp[i]<<" ";
            v[i].clear(); dis[i] = dp[i] = 1e9,f[i]=0;
        }
        cout<<"\n";
    }
}