F. 近似直径
每个测试的时间限制：2秒
内存限制：512兆字节

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), \dots, d(G_q)$。

然而，Jack 认为精确求出 $q+1$ 个图的直径可能很困难，因此他接受与正确答案相差不超过两倍的近似答案。形式化地说，Jack 想要找到一个正整数序列 $a_0, a_1, a_2, \dots, a_q$，使得对于每个 $i$ 满足：

$$\left\lceil \frac{d(G_i)}{2} \right\rceil \le a_i \le 2 \cdot d(G_i). $$

Hacks
本题不允许进行 Hack。

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

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

接下来 $q$ 行描述更新。第 $i$ 行包含两个整数 $u'_i$, $v'_i$（$1 \le u'_i, v'_i \le n$），表示在第 $i$ 次更新中添加的边所连接的两个顶点。

重要提示：出于测试目的，输入数据在以上所述格式之后可能包含一些额外的行。这些额外行将被检查器用于验证你的答案。它们不属于测试数据的一部分，你不应以任何方式使用它们，甚至可以忽略不读。

输出
打印 $q+1$ 个正整数 $a_0, a_1, a_2, \dots, a_q$。第 $i$ 个数与图 $G_i$ 的直径的差异不应超过两倍。

示例

输入 1

9 10 8
1 2
2 3
2 4
3 5
4 5
5 6
5 7
6 8
7 8
8 9
3 4
6 7
2 8
1 9
1 6
4 9
3 9
7 1

输出 1

10 6 5 6 2 4 2 2 1

输入 2

8 7 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
1 5
3 7
2 4
4 6
6 8
8 2
5 4
2 4
3 3
1 652997 124613 653029 653029 124613 124613 124613 648901 124613 653029

输出 2

7 5 4 4 4 3 3 3 3 3

注
在第一个示例中，$d(G_0), d(G_1), d(G_2), \dots, d(G_q)$ 的正确序列是 $6,6,6,3,3,3,2,2,2$。

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