#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<fstream>
using namespace std;
#define rep(i, a, n) for(int i = a; i <= n; ++ i)
#define per(i, a, n) for(int i = n; i >= a; -- i)
typedef long long ll;
typedef pair<int,int>PII;
const int N = 3e5 + 15;
const int mod = 1e9 + 7;
const double Pi = acos(- 1.0);
const int INF = 0x3f3f3f3f;
const int G = 3, Gi = 332748118;
ll qpow(ll a, ll b) { ll res = 1; while(b){ if(b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1;} return res; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
//

int n, m;
int head[N], cnt = 0;

vector<int> g[N][3]; //0, 1, 2 分别表示边，实边，虚边

bool vis[N];
int num[N], dis[N];
int dp[N];


void init(){
    for(int i = 1; i <= n; ++ i){
        for(int j = 0; j < 3; ++ j){
            g[i][j].clear();
        }

        dp[i] = INF;
    }
}

void SPFA(int st){
    queue<int> q;
    for(int i = 1; i <= n; ++ i){
        vis[i] = false; num[i] = 0; dis[i] = INF;
    }
    q.push(st); vis[st] = true; num[st] = 1, dis[st] = 0;
    while(q.size()){
        int u = q.front(); q.pop();
        vis[u] = false;
        for(int i = 0; i < g[u][0].size(); ++ i){
            int v = g[u][0][i];
            if(dis[v] > dis[u] + 1){
                dis[v] = dis[u] + 1;
                if(!vis[v]){
                    q.push(v); vis[v] = true;
                    if(++ num[v] >= n) return;
                }
            }
        }
    }
    return;
}

int dfs(int u){
    if(dp[u] != INF) return dp[u];
    for(int i = 0; i < g[u][1].size(); ++ i){
        int v = g[u][1][i];
        dp[u] = min(dp[u], dfs(v));
    }
    for(int i = 0; i < g[u][2].size(); ++ i){
        int v = g[u][2][i];
        dp[u] = min(dp[u], dis[v]);
    }
    dp[u] = min(dp[u], dis[u]);
    return dp[u];
}

int main()
{
    int T; scanf("%d",&T);
    while(T --){
        scanf("%d%d",&n,&m);
        init();
        for(int i = 1; i <= m; ++ i){
            int x, y; scanf("%d%d",&x, &y);
            g[x][0].push_back(y);
        }
        SPFA(1);

        for(int u = 1; u <= n; ++ u){
            for(int j = 0; j < g[u][0].size(); ++ j){
                int v = g[u][0][j];
                if(dis[u] >= dis[v]) g[u][2].push_back(v);
                else g[u][1].push_back(v); 
            }
        }

        for(int i = 1; i <= n; ++ i){
            if(dp[i] == INF){
                dp[i] = dfs(i);
            }
        }
        for(int i = 1; i <= n; ++ i){
            if(i == n) printf("%d\n",dp[i]);
            else printf("%d ",dp[i]);
        }
    }
    return 0;
}