#include<bits/stdc++.h>
#define FOR(i,l,r) for(int i=l;i<=r;i++)
#define ROF(i,l,r) for(int i=l;i>=r;i--)
#define lson k<<1,l,mid
#define rson k<<1|1,mid+1,r
#define r(x) read(x)
#define rr(x,y) read(x);read(y)
#define rrr(x,y,z) read(x);read(y);read(z)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
#define sss(str) scanf("%s",str+1)
using namespace std;
typedef long long LL;
typedef pair<int,int> pt;
const int N=2e5+5;
const int M=2e3+5;
const int mod=1e9+7;
const int INF=2e9;
const double eps=1e-8;
const double pi=acos(-1);
template <class T>
inline void read(T &x) {
    char c;x = 1;
    while ((c = getchar()) < '0' || c > '9') if (c == '-') x = -1;
    T res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9') res = res * 10 + c - '0';
    x *= res;
}
int n,m;
char str[N];
vector<int> v[N];
int dis[N],dp[N];
bool vis[N];
void bfs(int x)
{
    FOR(i,1,n) vis[i]=0;
    queue<pt> q;
    q.push(mp(x,0));
    vis[x]=1;
    while(q.size()){
        pt now=q.front();
        q.pop();
        dis[now.fi]=now.se;
        for(int nxt:v[now.fi]){
            if(!vis[nxt]){
                vis[nxt]=1;
                q.push(mp(nxt,now.se+1));
            }
        }
    }
}
void dfs(int x)
{
    vis[x]=1;
    dp[x]=dis[x];
//    cout<<dis[x]<<' '<<endl;
    for(int y:v[x]){
        if(!vis[y]&&dis[x]<dis[y]){
            dfs(y);
        }
        if(dis[x]<dis[y]){
            dp[x]=min(dp[x],dp[y]);
        }
        else{
            dp[x]=min(dp[x],dis[y]);
        }
    }
}
void solve(int cas)
{
    rr(n,m);
    FOR(i,1,n){
        v[i].clear();
    }
    FOR(i,1,m){
        int a,b;
        rr(a,b);
        v[a].pb(b);
        dis[i]=0;
    }
    bfs(1);
    FOR(i,1,n) vis[i]=0;
    dfs(1);
    FOR(i,1,n) cout<<dp[i]<<' ';
    cout<<endl;
}
int main()
{
    int t;
    r(t);
//    t=1;
//    init();
    FOR(i,1,t){
        solve(i);
    }
    return 0;
}
