/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <unordered_map>
using namespace std;
struct edge{
  int u;
  int v;
};
class GMovingToTheCapital {
public:
    unordered_map<int,vector<int>> adj;
    unordered_map<int,vector<int>> adjBReverse;
    int n, m;
    vector<int> dp;
    vector<int> v;
    vector<int> hv;
    vector<int> bfs(){
      vector<int> distances(n);
      int hasVisited[n];
      for(int i = 0; i < n; i++){
        hasVisited[i] = false;
      }
      priority_queue<pair<int,int>> pq; //-dist followed by our node
      pq.push({0,0});
      while(!pq.empty()){
        int i = pq.top().second;
        int dst = pq.top().first;
        distances[i] = -dst;
        hasVisited[i] = true;
        pq.pop();
        for(int j: adj[i]){
          if(hasVisited[j]){
            continue;
          }
          pq.push({dst - 1, j});
          hasVisited[j] = true;
        }
      }
      return distances;
    }
    vector<int> changed;
    void change(int vert, int val){
      hv[vert] = true;
      dp[vert] = min(dp[vert],val);
      changed.push_back(vert);
      for(int i: adjBReverse[vert]){
        if(!hv[i]){
          change(i,val);
        }
      }

    }
    void f(std::istream& in, std::ostream& out) {
      vector<edge> edges;
      in >> n >> m;
      for(int i = 0; i < m; i++){
        int u, v;
        in >> u >> v;
        u--;
        v--;
        adj[u].push_back(v);
      }
      v = bfs();
      for(int i = 0; i < n; i++){
        for(int j: adj[i]){
          if(v[i] < v[j]){
            adjBReverse[j].push_back(i);
          }else{
            edges.push_back({i,j});
          }
        }
      }
      dp.resize(n);
      hv.resize(n);
      for(int i = 0; i < n; i++){
        dp[i] = v[i];
        hv[i] = false;
      }

      for(auto e: edges){
        change(e.u, v[e.v]);
        for(int j: changed){
          hv[j] = false;
        }
        changed.clear();
      }
      for(int i = 0; i < n; i++){
        out << dp[i] << " ";
      }
      out << '\n';
    }
	void solve(std::istream& in, std::ostream& out) {
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
      int t;
	  in >> t;
	  while(t--){
	    f(in, out);
        dp.clear();
        v.clear();
        hv.clear();
        adj.clear();
        adjBReverse.clear();
	  }
	}
};


int main() {
	GMovingToTheCapital solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}
