#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m;
int dis[N];
int D[N];
template<typename T> void read(T& x)
{  
	int f = 1; x = 0; char s = getchar();
	while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
	while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
	x *= f;
}
namespace FD 
{
	const int V = 2e5 + 5;
	const int M = 2e5 + 5;
	int n;
	int ap[V], an, a[M], al[M];
	bool vis[V];
	int s[N], sn , p, pn;

	void FDinit(int _n)
	{
		n = _n;
		for (int i = 0; i <= n; ++i) ap[i] = 0, vis[i] = false, dis[i] = n + 1;
		an = 0;
	}
	inline void FDaddedge(int u, int v)
	{
		an++;
		a[an] = v;
		al[an] = ap[u];
		ap[u] = an;
	}

	void BFS()
	{
		dis[1] = 0; vis[1] = true;
		int u, v;
		for (s[1] = p = pn = 1; p <= pn && p < n; p++)
		{
			v = s[p];
			for (int j = ap[v]; j; j = al[j])
			{
				u = a[j];
				if (vis[u]) continue;
				else
				{
					pn++;
					s[pn] = u;
					dis[u] = dis[v] + 1;
					vis[u] = true;
				}
			}
		}
	}
	
}

int x[N], y[N];
int ap[N], a[N * 2], al[N * 2], an;
bool vis[N];

void init(int n)
{
	for (int i = 0; i <= n; i++) ap[i] = 0, D[i] = dis[i], vis[i] = false;
	an = 0;
}

void addedge(int u, int v)
{
	an++;
	a[an] = v;
	al[an] = ap[u];
	ap[u] = an;
}

int dfs(int p, int fp)
{
	if (vis[p]) return D[p];
	vis[p] = true;
	for (int j = ap[p]; j; j = al[j])
	{
		if (a[j] == fp) continue;
		D[p] = min(D[p], dfs(a[j], p));
	}
	return D[p];
}

int solve()
{
	read(n); read(m);

	FD::FDinit(n);
	for (int i = 1; i <= m; ++i)
	{
		read(x[i]); read(y[i]);
		
		FD::FDaddedge(x[i], y[i]);
	}
	FD::BFS();

	init(n);
	for (int i = 1; i <= m; ++i)
	{
		if (dis[x[i]] < dis[y[i]]) addedge(x[i], y[i]);
		else D[x[i]] = min(dis[y[i]], D[x[i]]);
	}
	dfs(1, 0);
	for (int i = 1; i <= n; i++) printf("%d ", D[i]);
	printf("\n");
	return 0;
}

int main()
{
	int _T = 1;
	read(_T);
	while (_T--)
	{
		solve();
	}
	return 0;
}