#include <bits/stdc++.h> 
using namespace std;
#define ll                long long
#define pb                push_back
#define vi                vector<int>
#define vl                vector<long long>
#define vll               vector<pair<long long,long long>>
#define vii               vector<pair<int,int>>
#define vvi               vector<vector<int>>
#define maxq(x)           priority_queue<x>
#define minq(x)           priority_queue<x,vector<x>,greater<x>>
#define graph             map<int,vi>
#define vvl               vector<vector<long long>>
#define pb                push_back
#define ppb               pop_back
#define pf                push_front
#define ppf               pop_front
#define all(x)            (x).begin(),(x).end()
#define uniq(v)           (v).erase(unique(all(v)),(v).end())
#define sz(x)             (int)((x).size())
#define f                 first
#define s                 second
#define pii               pair<int,int>
#define rep(i,a,b)        for(int i=a;i<b;i++)
#define mem1(a)           memset(a,-1,sizeof(a))
#define mem0(a)           memset(a,0,sizeof(a))
#define ppc               __builtin_popcount
#define ppcll             __builtin_popcountll
# define quick ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
graph g;
int dfs(int node,vi &vis,vi &dist,vi &ans)
{   
    if(vis[node])
    return ans[node];
    
    vis[node] = 1;
    int temp = INT_MAX;
    for(auto nbr : g[node])
    {
        if(dist[nbr]<=dist[node])
        temp = min(temp,dist[nbr]);
        else
        temp = min(temp,dfs(nbr,vis,dist,ans));
    }
    return ans[node] = min(ans[node],temp);
}
int main() 
{  
  quick
  int t = 1;
  cin>>t;
  while(t--)
  {
   int n,m;
   cin>>n>>m;
   g.clear();
   rep(i,0,m)
   {
       int x,y;
       cin>>x>>y;
       g[x].pb(y);
   }
   vi dist(n + 1,INT_MAX);
   dist[1] = 0;
   queue<int> q;
   q.push(1);
   while(!q.empty())
   {
       int node = q.front();
       q.pop();
       for(auto nbr : g[node])
       {
           if(dist[nbr]>dist[node] + 1)
           {
               dist[nbr] = dist[node] + 1;
               q.push(nbr);
           }
       }
   }
   vi ans(n + 1,0);
   vi vis(n + 1,0);
   for(int i = 2;i<=n;i++)
   ans[i] = dist[i];
   for(int i = 2;i<=n;i++)
   {
       if(!vis[i])
       dfs(i,vis,dist,ans);
   }
   for(int i =1;i<=n;i++)
   cout<<ans[i]<<" ";
   cout<<endl;
   
  }
  return 0;
   
} 