#include <bits/stdc++.h>

using namespace std;

void bfs (int node, vector<vector<int>> &graph, vector<bool> &vis, vector<int> &dist){
	
	deque<int> Q;
	Q.push_back(node);
	vis[node] = true;
	dist[node] = 0;
	while (!Q.empty()){
		auto node = Q.front();
		Q.pop_front();
		for (auto adj : graph[node]){
			if (!vis[adj]){
				vis[adj] = true;
				dist[adj] = dist[node] + 1;
				Q.push_back(adj);
			}
		}
	}
}

int dfs2(int node, vector<vector<int>> &graph, vector<bool> &vis2, vector<int> &dist, vector<int> &sol){
	if (vis2[node])
		return sol[node];
	vis2[node] = true;
	sol[node] = dist[node];
	for (auto adj : graph[node]){
		if (dist[adj] > dist[node])
			sol[node] = min(sol[node], dfs2(adj, graph, vis2, dist, sol));
		else
			sol[node] = min(sol[node], dist[adj]);
	}
	return sol[node];
}

int main(){
	int T;
	cin >> T;
	for (int t = 0; t < T; t++){
		long long N, M, K;
		cin >> N >> M;
		vector<vector<int>> graph(N, vector<int>());
		vector<bool> vis(N, false);
		vector<int> dist(N, 0);
		for (int i = 0; i < M; i++){
			int da, a;
			cin >> da >> a;
			da--;
			a--;
			graph[da].push_back(a);
		}
		bfs(0, graph, vis, dist);
		vector<bool> vis2(N, false);
		vector<int> sol(N);
		for (int i = 0; i < N; i++)
			sol[i] = dist[i];
		for (int i = 0; i < N; i++){
			cout << dfs2(i, graph, vis2, dist, sol) << ' ';
		}
		cout << '\n';
	}
}