AdditionalFile5660.zip

#5660. 「POI2026 R3」Rozbudowa Bajtocji

标签: 传统 | 时间限制: 3500 ms | 内存限制: 512 MiB |

题目描述

题目译自 XXXIII Olimpiada Informatyczna – III etap Rozbudowa Bajtocji

著名的历史学家 Bajtosz 正在整理关于比特托邦道路扩建的资料。很久以前，比特托邦只有 $n$ 个互不相连的村庄。而现在，那里已经有了 $m$ 条双向道路，并且可以从任何一个村庄通过已建成的道路到达另一个村庄。根据历史记录，Bajtosz 确定比特托邦每年恰好新建一条道路。他还得知了这些道路修建的先后顺序。在每条道路修建完成后，按照长久以来的传统，比特托邦的居民都会举行一场盛大的游行。每次游行必须从同一个村庄开始并结束，且必须经过至少一条道路，同时同一条道路在单次游行中不能经过超过一次。

Bajtosz 现在想知道，对于每一条道路，最早可能在第几年出现包含该道路的游行。他请你为每条道路确定这一信息。

输入格式

第一行包含两个整数 $n$ 和 $m$ $(2 \leq n \leq 1000000; n-1 \leq m \leq 1000000)$，分别表示村庄的数量和道路的数量。

接下来的 $m$ 行包含了在比特托邦修建的各条道路的描述。其中的第 $i$ 行包含两个整数 $u_i$ 和 $v_i$ $(1 \leq u_i, v_i \leq n, u_i \neq v_i)$，表示在第 $i$ 年修建了连接村庄 $u_i$ 和 $v_i$ 的双向道路。

输出格式

输出应包含一行，由 $m$ 个整数组成，整数之间用单个空格分隔。其中第 $i$ 个整数应等于最早可能出现包含第 $i$ 年修建的道路的游行的年份。如果该道路永远不可能出现在游行中，则输出 $-1$。

样例 1

输入

5 7
3 1
1 2
2 1
3 4
2 4
5 3
1 5

输出

5 3 3 5 5 7 7

在第一个样例中，修建了 $3$ 条道路后，游行可以按以下路线进行：$1 \xrightarrow{2} 2 \xrightarrow{3} 1$（箭头上的数字是所经过道路的修建年份）。修建了 $5$ 条道路后，游行可以按以下路线进行：$1 \xrightarrow{1} 3 \xrightarrow{4} 4 \xrightarrow{5} 2 \xrightarrow{2} 1$。修建完所有 $7$ 条道路后，游行可以按以下路线进行：$1 \xrightarrow{7} 5 \xrightarrow{6} 3 \xrightarrow{1} 1$。在第二个样例中，第 $2$ 年修建的道路永远无法成为游行的一部分。

样例 2

输入

3 3
1 2
1 3
2 1

输出

3 -1 3

样例 3

输入

6 7
1 2
2 5
2 3
4 3
1 4
1 5
5 6

输出

5 6 5 5 5 6 -1

附加样例

样例 $\texttt{0a}, \texttt{0b}, \texttt{0c}$ 即为上述样例。此外：

• $0d$：$n=1000000, m=1000000$，对于 $1 \leq i < m$ 有 $u_i = i, v_i = i+1$，且 $u_m = n, v_m = 1$。

数据范围与提示

详细子任务附加限制及分值如下表所示。