CF1804F.Approximate Diameter

Jack has a graph of $n$ vertices and $m$ edges. All edges are bidirectional and of unit length. The graph is connected, i. e. there exists a path between any two of its vertices. There can be more than one edge connecting the same pair of vertices. The graph can contain self-loops, i. e. edges connecting a node to itself.

The distance between vertices $u$ and $v$ is denoted as $\rho(u, v)$ and equals the minimum possible number of edges on a path between $u$ and $v$. The diameter of graph $G$ is defined as the maximum possible distance between some pair of its vertices. We denote it as $d(G)$. In other words, $$d(G) = \max_{1 \le u, v \le n}{\rho(u, v)}.$$

Jack plans to consecutively apply $q$ updates to his graph. Each update adds exactly one edge to the graph. Denote as $G_i$ the graph after exactly $i$ updates are made. Jack wants to calculate $q + 1$ values $d(G_0), d(G_1), d(G_2), \ldots, d(G_q)$.

However, Jack suspects that finding the exact diameters of $q + 1$ graphs might be a difficult task, so he is fine with approximate answers that differ from the correct answers no more than twice. Formally, Jack wants to find a sequence of positive integers $a_0, a_1, a_2, \ldots, a_q$ such that $$\left\lceil \frac{d(G_i)}{2} \right\rceil \le a_i \le 2 \cdot d(G_i)$$ for each $i$.

Hacks

You cannot make hacks in this problem.

Jack 有一个包含 $n$ 个顶点和 $m$ 条边的图。所有边均为无向边，且长度均为 1。该图是连通的，即任意两个顶点之间均存在一条路径。同一对顶点之间可能存在多条边。图中也可能包含自环，即连接某个顶点与其自身的边。

顶点 $u$ 与 $v$ 之间的距离记为 $\rho(u, v)$，其值等于 $u$ 与 $v$ 之间路径所含边数的最小可能值。图 $G$ 的直径定义为图中某对顶点之间可能的最大距离，记作 $d(G)$。换言之，

$$d(G) = \max_{1 \le u, v \le n}{\rho(u, v)}.$$

Jack 计划对该图连续执行 $q$ 次更新操作，每次更新恰好向图中添加一条边。记 $G_i$ 为恰好执行 $i$ 次更新后的图。Jack 希望计算出 $q + 1$ 个值：$d(G_0), d(G_1), d(G_2), \ldots, d(G_q)$。

然而，Jack 怀疑精确求出 $q + 1$ 个图的直径可能较为困难，因此他接受近似答案，只要每个近似值与真实直径的偏差不超过真实值的两倍即可。形式化地说，Jack 希望找出一个正整数序列 $a_0, a_1, a_2, \ldots, a_q$，使得对每个 $i$ 均满足

\left\lceil \frac{d(G_i)}{2} \right\rceil \le a_i \le 2 \cdot d(G_i)$$。 Hack 本题不允许进行 Hack。

The first line of the input contains three integers $n$, $m$, and $q$ ($2 \leq n \leq 10^5$, $n - 1 \leq m \leq 10^5$, $0 \leq q \leq 10^5$), the number of vertices in the given graph, the number of edges and the number of updates, respectively.

Then follow $m$ lines describing the initial edges of the graph. The $i$-th of these lines contains two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$), the indexes of the vertices connected by the $i$-th edge.

Then follow $q$ lines describing the updates. The $i$-th of these lines contains two integers $u'_i$ and $v'_i$ ($1 \leq u'_i, v'_i \leq n$), the indexes of the vertices connected by the edge that is added to the graph in the $i$-th update.

Important note. For testing purposes, the input data may contain some extra lines after the mentioned input format. These will be used by the checker to verify your answer. They are not a part of the test data, you should not use them in any way and you can even omit reading them.

输入的第一行包含三个整数 $n$、$m$ 和 $q$（$2 \leq n \leq 10^5$，$n - 1 \leq m \leq 10^5$，$0 \leq q \leq 10^5$），分别表示给定图中的顶点数、边数以及更新操作次数。

接下来 $m$ 行描述图的初始边。其中第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$），表示第 $i$ 条边所连接的两个顶点的编号。

随后 $q$ 行描述更新操作。其中第 $i$ 行包含两个整数 $u'_i$ 和 $v'_i$（$1 \leq u'_i, v'_i \leq n$），表示在第 $i$ 次更新中加入图中的边所连接的两个顶点的编号。

重要提示：出于测试目的，输入数据末尾可能包含若干额外的行（超出上述格式说明的部分）。这些额外行将被评测器用于验证你的答案。它们不属于测试数据，你不应以任何方式使用它们，甚至可以完全忽略读取它们。

Print a sequence of $q + 1$ positive integers $a_0, a_1, a_2, \ldots, a_q$. The $i$-th of these integers should differ from the diameter of graph $G_i$ no more than twice.

输出一个由 $q + 1$ 个正整数组成的序列 $a_0, a_1, a_2, \ldots, a_q$。其中第 $i$ 个整数与图 $G_i$ 的直径之差的绝对值至多为 $2$。

In the first example, the correct sequence of $d(G_0), d(G_1), d(G_2), \ldots, d(G_q)$ is $6, 6, 6, 3, 3, 3, 2, 2, 2$.

In the second example, the input contains an extra line that you can omit reading. It is not a part of the test and will be used for verifying your answer. The output of the second example contains the correct values of $d(G_i)$.

在第一个例子中，$d(G_0), d(G_1), d(G_2), \ldots, d(G_q)$ 的正确序列为 $6, 6, 6, 3, 3, 3, 2, 2, 2$。

在第二个例子中，输入包含一行额外内容，你可以忽略该行的读取。它不属于测试用例，仅用于验证你的答案。第二个例子的输出中包含了正确的 $d(G_i)$ 值。