In conclusion, this problem can be solved by constructing a DFS tree rooted at vertex \(1\) in the given graph, and outputting the depth of each vertex.

For DFS trees, please refer to the first part of this editorial.

Using properties of the DFS tree, the edges connected to vertex \(v\) in the given graph can be classified as follows.

1. The edge on the DFS tree connecting \(v\) and its direct parent (every vertex except the root of the DFS tree has exactly one such edge)
2. Edges on the DFS tree connecting \(v\) and its direct children
3. Edges not included in the DFS tree

By considering edges of type 1., for every vertex other than vertex \(1\), there exists exactly one edge connecting to a vertex whose depth in the DFS tree is exactly \(1\) smaller.
An edge of type 2. connects the vertex to a vertex of greater depth, so we do not need to consider it while writing the DFS tree’s depth.
For an edge \((v,u)\) of type 3., by the properties of DFS trees, \(v\) and \(u\) are in an ancestor-descendant relationship. Furthermore, these two vertices cannot be a direct parent-child pair (if they were, the graph would contain a multi-edge). Therefore, the difference in depth between \(v\) and \(u\) on the DFS tree is always \(2\) or more.

The above shows that writing the DFS tree’s depth on each vertex is a valid construction.

The time complexity of this solution is \(O(N+M)\).

Sample Implementation (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;
}