#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define pb push_back
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a) memset(a, 0, sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
typedef pair<ll, ll> P;
const int maxn = 2e5 + 10;
int n, m;
vector<int> vec[maxn];
int dis[maxn];
bool vis[maxn];
int dp[maxn];
void bfs()
{
    queue<P> q;
    dis[1] = 0;
    q.push(P{1, 0});
    while (q.size())
    {
        P p = q.front();
        q.pop();
        int po = p.first;
        int d = p.second;
        if (vis[po])
            continue;
        vis[po] = 1;
        dis[po] = d;
        for (auto v : vec[po])
        {
            q.push(P(v, d + 1));
        }
    }
}
void dfs(int x)
{
    vis[x] = 1;
    dp[x] = dis[x];
    for(auto u:vec[x])
    {
        if(!vis[u]&& dis[x]<dis[u])
            dfs(u);
        if(dis[x]<dis[u])
            dp[x] = min(dp[x], dp[u]);
        else
            dp[x] = min(dp[x], dis[u]);
    }
}
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        vec[i].clear(), dis[i] = 0, vis[i] = 0, dp[i] = 1e7;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        vec[x].pb(y);
    }
    bfs();
    for (int i = 1; i <= n; i++)
        vis[i] = 0;
    dfs(1);
    for (int i = 1; i <= n;i++)
        cout << dp[i] << " ";
    cout << endl;
}
int main()
{
    IOS;
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}