宝宝题。设 $n,m$ 同阶。

考察相邻的一次放置和升起动作，发现叉车的位置等价于移动了两步，设叉车放置时位于 $x$，升起时位于 $y$，货物放置在 $t$，能完成这样的一次操作要求存在两条边 $(x,t),(t,y)$ 并且删除点 $t$ 后 $x$ 依然可达 $y$。所以我们开一张新图，对所有能走的 $(x,y)$ 点对之间连一条长度为 $2$ 的边，那么问题变成无向无权图单源最短路。暴力枚举 $x,y$ 建新图跑 BFS 复杂度 $O(n^2)$。

考虑优化建图，相当于要求 $x,y$ 在同一个点双内部，所以我们对一个点双 $s$ 内所有点 $u$ 开一个新点 $p(s,u)$，对于点双内部所有边 $(u,v)$，新图上连接 $(p(s,u),v)$ 以及 $(u,p(s,v))$，那么合法的 $(x,y)$ 点对之间距离依然是 $2$，但是边数降低到 $O(n)$，然后跑 BFS 即可。

问题变成求出每条边所属的点双，显然非割点连出去的所有边和他本身同属一个边双。接下来考察割点。我们在 Tarjan 过程中可以求出 $b_i$ 表示割点 $i$ 在 dfs 树上与他的父亲之间的连边所属的点双。我们枚举割点 $u$ 以及一条出边 $(u,v)$，如果 dfs 树上深度 $d_u > d_v$，说明是返祖边，此时该边所属点双为 $b_u$；如果深度 $d_u < d_v$，说明是连往子树内的，此时该边所属点双为 $b_v$。其实一开始写了一个假复杂度做法好像也能过，但是菊花图直接给叉了。

#include <bits/stdc++.h>
#define LL long long
#define ull unsigned long long
#define uint unsigned int
using namespace std;
const int N = 5e5 + 10;
int n, m, ptot; vector<int> G[N];

vector<int> DCC[N]; int tot; bool cut[N];
int dfn[N], stk[N], tp, low[N], dfncnt, depth[N], bel[N];
void Tarjan(int u, int f) {
	dfn[u] = low[u] = ++ dfncnt; stk[++ tp] = u; depth[u] = depth[f] + 1;
	if (u == 1 && G[u].size() == 0) { cut[u] = true; DCC[++ tot].push_back(u); }
	int c = 0;
	for (int v : G[u]) if (v != f) {
		if (!dfn[v]) {
			Tarjan(v, u); low[u] = min(low[u], low[v]);
			if (low[v] >= dfn[u]) {		
				++ tot; ++ c; if (c > 1 || u != 1) cut[u] = true;
				while (stk[tp] != v) bel[stk[tp]] = tot, DCC[tot].push_back(stk[tp --]);
				DCC[tot].push_back(stk[tp --]); bel[v] = tot;
				DCC[tot].push_back(u);
			}
		} else low[u] = min(low[u], dfn[v]);
	} return ;
}

vector<int> vec[N * 3]; unordered_map<LL, int> idx;
#define id(x, y) (1ll * x * 0x325609 + y)

int dist[N * 3]; bool vis[N * 3];
void BFS() {
	for (int i = 1; i <= ptot; i ++) dist[i] = 1e9, vis[i] = false;
	dist[1] = 0; queue<int> q; q.push(1); vis[1] = true;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int v : vec[u]) if (!vis[v])
			dist[v] = dist[u] + 1, vis[v] = 1, q.push(v);
	} return ;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
	int _; cin >> _;
	while (_ --) {
		cin >> n >> m; ptot = n; idx.clear();
		for (int i = 1, u, v; i <= m; i ++) {
			cin >> u >> v; G[u].push_back(v), G[v].push_back(u);
		} Tarjan(1, 0); 
		for (int i = 1; i <= n; i ++) if (!cut[i]) {
			idx[id(i, bel[i])] = ++ ptot;
			for (int v : G[i]) vec[v].push_back(ptot), vec[ptot].push_back(v);
		}
		for (int i = 1; i <= n; i ++) if (cut[i]) {
			for (int v : G[i]) {
				int t = 0;
				if (depth[v] > depth[i]) {
					if (idx.find(id(i, bel[v])) == idx.end()) t = idx[id(i, bel[v])] = ++ ptot;
					else t = idx[id(i, bel[v])];
				} else {
					if (idx.find(id(i, bel[i])) == idx.end()) t = idx[id(i, bel[i])] = ++ ptot;
					else t = idx[id(i, bel[i])];
				} vec[t].push_back(v), vec[v].push_back(t);
			}
		}
		BFS();
		for (int i = 2; i <= n; i ++)
			cout << (vis[i] ? dist[i] : -1) << " \n"[i == n];
		for (int i = 1; i <= n; i ++) G[i].clear(), dfn[i] = low[i] = 0, cut[i] = false;
		for (int i = 1; i <= tot; i ++) DCC[i].clear();
		for (int i = 1; i <= ptot; i ++) vec[i].clear(), vis[i] = false;
		tp = dfncnt = tot = 0;
	}	
	return 0;
}