//EK ONKAR
#include <bits/stdc++.h>

using namespace std;

/******************************MACROS******************************/

#define int long long
#define ld long double
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define vt vector
#define pb push_back
#define F first
#define S second
#define u_s unordered_set
#define u_m unordered_map
#define p_q priority_queue
#define m_p make_pair
#ifdef ONLINE_JUDGE
#define endl '\n'
#endif

/******************************TEMPLATE******************************/

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef ONLINE_JUDGE
    ~debug() { cerr << endl; }
    eni(!=) cerr << boolalpha << i; ris; }
    eni(==) ris << range(begin(i), end(i)); }
    sim, class b dor(pair < b, c > d) {
        ris << "(" << d.first << ", " << d.second << ")";
    }
    sim dor(rge<c> d) {
        *this << "[";
        for (auto it = d.b; it != d.e; ++it)
            *this << ", " + 2 * (it == d.b) << *it;
        ris << "]";
    }
#else
    sim dor(const c&) { ris; }
#endif
};
#define deb(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

/******************************ALGORITHMS******************************/

int __pow(int x, int y, int M) {int res = 1;while(y>0){if(y&1) res = (res*x)%M; y>>=1; x = (x*x)%M;}return res%M;}
int __pow(int x, int y) {int res = 1;while(y>0){if(y&1) res = (res*x); y>>=1; x = (x*x);}return res;}
int mi(int x, int M) {return __pow(x, M-2, M);}
void umax(int &a, int b) {a = max(a, b);}
void umin(int &a, int b) {a = min(a, b);}

/******************************main*code******************************/

const int N = 2e5+2, inf = 1e18, M = 998244353;

int Test, n, m, dp[N], d[N];
bool ok = 1, vis[N];
vt<int> g[N];
p_q<pair<int, int>> pq;
void dfs(int u)
{
    bool is_leaf = 1;
    vis[u] = 1;
    for(int v:g[u])
    {
        is_leaf = 0;
        if(!vis[v] && d[u] < d[v])
            dfs(v);
        if(d[u] < d[v])
            dp[u] = min(dp[u], dp[v]);
        else
            dp[u] = min(dp[u], d[v]);
    }
    if(is_leaf) dp[u] = d[u];
}

void test_case()
{
    cin >> n >> m;
    for(int i = 1; i<=n; i++)
        g[i].clear(), d[i] = inf, vis[i] = 0;
    for(int i = 1; i<=m; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
    }
    pq.push({0, 1});
    d[1] = 0;
    while(pq.size())
    {
        int u = pq.top().S;
        pq.pop();
        for (int v:g[u])
            if (d[v] > d[u] + 1)
                d[v] = d[u] + 1, pq.push({-d[v], v});
    }
    for(int i = 1; i<=n; i++)
        dp[i] = d[i];
    dfs(1);
    for(int i = 1; i<=n; i++)
        cout << dp[i] << " ";
    cout << endl;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    Test = 1;
    cin >> Test;
    while(Test--)
        test_case();
#ifndef ONLINE_JUDGE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s." << endl;
#endif
    return 0;
}
