P11102 [ROI 2022] 搬货 (Day 2)

翻译自 [ROI 2022 D2T3](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-roi-2022-day2.pdf)。 仓库操作员需要使用特殊叉车移动重箱。可以将仓库简化为 $n$ 个房间，通过 $m$ 条走廊连接。可以通过走廊从任意一个房间到达任意其他房间。房间编号从 $1$ 到 $n$。走廊 $i$ 直接连接房间 $u_i$ 和 $v_i$，可以双向移动。 叉车可以升降货物，如果不携带货物，可以在空房间和走廊之间移动。最初，叉车位于房间 $1$，并携带着升起的货物。叉车可以执行以下操作： 1. 如果叉车位于房间 $a$ 并且携带升起的货物，则可以将货物放置在房间 $b$，前提是房间 $a$ 和 $b$ 直接相连。完成此操作后，叉车不再携带货物并可以移动。 2. 如果叉车位于房间 $a$，货物放置在房间 $b$，并且房间 $a$ 和 $b$ 直接相连，则叉车可以在不移动的情况下升起货物。完成此操作后，叉车仍然位于房间 $a$ 并携带升起的货物，直到放下货物之前不能移动。 3. 如果叉车没有携带货物，则可以在走廊和房间之间移动，但不能通过放有货物的房间。

空车在房间之间移动非常快，比升降货物的速度快得多。因此，我们假设叉车执行第一或第二操作需要一单位时间，而第三个操作是瞬时完成的。对于每个房间 $p(2 \le p \le n)$，需要确定叉车从初始位置（在第一个房间且携带升起的货物）到达房间 $p$ 并继续携带升起的货物所需的最短时间，或者确定这是不可能的。

每个测试由多组数据组成。第一行给出一个整数 $t$（$1 \le t \le 100,000$），即数据的组数。接下来是每组数据的描述。 每组数据的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 500,000,1 \le m \le 500,000$），即仓库中房间和走廊的数量。 接下来的 $m$ 行每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i,v_i \le n,u_i \ne v_i$），表示第 $i$ 条走廊连接的两个房间编号。保证每对通过走廊连接的房间只会出现一次（或者说每个走廊只输入一次）。保证如果所有房间都是空闲的，则可以通过走廊从任意房间到达任意其他房间，即由仓库简化成的图是联通的。 用 $\sum n$ 表示每一组数据中 $n$ 的总和，用 $\sum m$ 表示 $m$ 的总和，保证 $\sum n \le 500,000,\sum m \le 500,000$。

对于每组输入，输出 $n - 1$ 个数字，其中第 $i$ 个数字应该等于叉车从房间 $1$ 开始到房间 $i+1$（同时继续携带升起的货物）需要升降货物的最小次数（也就是最短时间）。如果无法实现，则第 $i$ 个数字应为 $-1$。

部分样例解释： 在第四组数据中，为了使叉车从房间 $1$ 开始（携带升起的货物）尽快到达房间 $4$（并继续携带升起的货物），可以执行以下操作： - 将货物放置在房间 $2$。需要花费一单位时间。 - 移动到房间 $3$。不需要花费时间。 - 从房间 $2$ 中升起货物。需要花费一单位时间。 - 将货物放置在房间 $9$。需要花费一单位时间。 - 移动到房间 $6$。不需要花费时间。 - 从房间 $9$ 中升起货物。需要花费一单位时间。 - 将货物放置在房间 $5$。需要花费一单位时间。 - 移动到房间 $4$。不需要花费时间。 - 从房间 $5$ 中升起货物。需要花费一单位时间。 总共需要花费 $6$ 个单位时间。 | Subtask | 分值 | $\sum n\le$ | $\sum m\le$ | 特殊性质 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $16$ | $1000$ | $2000$ | | | $2$ | $18$ | $1000$ | $100000$ | | | $3$ | $14$ | $5000$ | $500000$ | | | $4$ | $17$ | $500000$ | $500000$ | 对于任意 $1\le i\le n-1$，存在一条走廊连接 $i$ 和 $i+1$ 号房间，且 $1$ 和 $n$ 号房间也有走廊连接 | | $5$ | $12$ | $500000$ | $500000$ | 每个房间最多有 $3$ 条走廊 | | $6$ | $23$ | $500000$ | $500000$ | |