結論から言うと、与えられるグラフにて頂点 \(1\) を根とする DFS 木を \(1\) つ構築した上で、各頂点の深さを出力するとこの問題に正解できます。

DFS 木について、 こちらの解説の導入部 を参照してください。

DFS 木の性質を利用すると、与えられるグラフにて頂点 \(v\) に繋がる辺は以下の通り分類できます。

1. DFS 木上で \(v\) とその直接の親とを結ぶ辺 ( DFS 木上の根を除き、全ての頂点にちょうど \(1\) 本このような辺が存在します )
2. DFS 木上で \(v\) とその直接の子とを結ぶ辺
3. DFS 木に含まれない辺

1. の辺を考慮することで、頂点 \(1\) 以外の全ての頂点について、 DFS 木上での深さがちょうど \(1\) 小さい頂点に繋がる辺が \(1\) つ存在します。
2. の辺はその頂点からより深さの大きい頂点に繋がる辺であるため、 DFS 木の深さを書き込むという前提では考えなくてよいです。
3. の辺 \((v,u)\) について、 DFS 木の性質から、\(v\) と \(u\) とは祖先の関係にあります。更に、この \(2\) 頂点が直接の親子であることもありません(もし直接の親子であった場合グラフに多重辺が存在することになってしまいます)。なので、 \(v\) と \(u\) との DFS 木上での深さの差は必ず \(2\) 以上です。

以上より、各頂点に DFS 木の深さを書き込むことが正当な構築法のひとつであることが示されました。

本解法の時間計算量は \(O(N+M)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using Graph=vector<vector<int>>;

void dfs(int v,int dep,vector<int> &res,Graph &g){
  res[v]=dep;
  for(auto &nx : g[v]){
    if(res[nx]!=-1){continue;}
    dfs(nx,dep+1,res,g);
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while(t--){
    int n,m;
    cin >> n >> m;
    Graph g(n);
    for(int i=0;i<m;i++){
      int u,v;
      cin >> u >> v;
      u--; v--;
      g[u].push_back(v);
      g[v].push_back(u);
    }
    vector<int> res(n,-1);
    dfs(0,0,res,g);
    for(int i=0;i<n;i++){
      if(i){cout << " ";}
      cout << res[i];
    }cout << "\n";
  }
  return 0;
}