A-Connect Graph_牛客挑战赛64

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

有一个 $n$ 个点， $m_1$ 条边的无向图，现在要在这个图上按顺序添加 $m_2$ 条无向边，每新添加一条边需要花费 $1$ 天时间，问每个点最早何时与 $1$ 号点联通。

注：以未加“之后的 $m_2$ 条边”时作为第 $0$ 天，即第 $0$ 天时图上就有 $m_1$ 条边，加入第一条边的时间为第一天，若加入第 $i$ 条边之后某个点与 $1$ 号点联通，且在此之前该点与 $1$ 号点不联通，则称该点与点 $1$ 联通的时间为 $i$ 。

第一行一个整数 $n (3\le n\le2\times10^5)$ 。

第二行两个整数 $m_1,m_2 (1\le m_1+m_2 \le 4\times10^5)$ 。

下面 $m_1$ 行，一行两个整数 $u,v (1\le u,v \le n)$ ，表示初始的一条边。

下面 $m_2$ 行，一行两个整数 $u,v (1\le u,v \le n)$ ，表示新添加的一条边。

共  行，对于第  行输出一个整数表示点  与点  联通的时间，如果永远无法与点  联通，输出 。

示例1

复制

复制

如图，其中边上的数字为加入这条边的时间。