#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <queue>

using namespace std;

struct Vertex {
    int v;
    int next;
};

constexpr int maxn = 200000;
constexpr int maxm = 200000;
int g[maxn];
Vertex e[maxm];
bool u[maxn];
int dist[maxn];
int dist2[maxn];
int dist3[maxn];

void dfs(int v) {
    dist3[v] = dist2[v];
    for (int p = g[v]; p != -1; p = e[p].next) {
        int v2 = e[p].v;
        if (dist[v2] == dist[v] + 1) {
            if (!u[v2]) {
                u[v2] = true;
                dfs(v2);
            }
            dist3[v] = min(dist3[v], dist3[v2]);
        }
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    fill(g, g + n, -1);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        e[i] = { b - 1, g[a - 1] };
        g[a - 1] = i;
    }
    queue<int> q;
    fill(dist, dist + n, -1);
    q.push(0);
    dist[0] = 0;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int p = g[v]; p != -1; p = e[p].next) {
            int v2 = e[p].v;
            if (dist[v2] == -1) {
                q.push(v2);
                dist[v2] = dist[v] + 1;
            }
        }
    }
    fill(dist2, dist2 + n, -1);
    for (int i = 0; i < n; ++i) {
        dist2[i] = dist[i];
        for (int p = g[i]; p != -1; p = e[p].next) {
            int v = e[p].v;
            dist2[i] = min(dist2[i], dist[v]);
        }
    }
    fill(u, u + n, false);
    fill(dist3, dist3 + n, -1);
    dfs(0);
    for (int i = 0; i < n; ++i) {
        cout << dist3[i] << ' ';
    }
    cout << '\n';
}

int main() {
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    cout << fixed << setprecision(15);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t;
    cin >> t;
    while (t--) solve();
}
