#include <bits/stdc++.h>
using namespace std;

const int N = 200000 + 9;
const int inf = 0x3f3f3f3f;

vector<int> G[N];

typedef pair<int, int> PII;

vector<PII> _G[N];

int dis[N], _dis[N];

void bfs(int s, int n){
    memset(dis, 0x3f, (n+5) * sizeof(*dis));
    queue<int> Q;
    Q.push(s);
    dis[s] = 0;
    while (!Q.empty()){
        int u = Q.front();
        Q.pop();
        for (int v : G[u]){
            if (dis[v] == inf){
                dis[v] = dis[u] + 1;
                Q.push(v);
            }
        }
    }
}

void dijkstra(int s, int n){
    memset(_dis, 0x3f, (n+5) * sizeof(*_dis));
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push({0, s});
    _dis[s] = 0;
    while (!pq.empty()){
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        for (auto it : _G[u]){
            int v = it.first;
            int w = it.second;
            if (d + w < _dis[v]){
                _dis[v] = d + w;
                pq.push({_dis[v], v});
            }
        }
    } 
}

void solve(){
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n + 1; ++i){
        G[i].clear();
        _G[i].clear();
    }
    for (int i = 1; i <= m; ++i){
        int u, v;
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
    }
    bfs(1, n);
    int s = n + 1;
    for (int i = 1; i <= n; ++i){
        int tmp = dis[i];
        for (int j : G[i]){
            tmp = min(tmp, dis[j]);
            if (dis[i] < dis[j]){
                _G[j].push_back({i, 0});
            }
        }
        _G[s].push_back({i, tmp});
    }
    dijkstra(s, n + 1);
    for (int i = 1; i <= n; ++i){
        printf("%d ", _dis[i]);
    }
    printf("\n");
}

int main(){
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}