Jack 有一个由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成的图。所有边都是双向的且具有单位长度。该图是连通的,i。 e.它的任意两个顶点之间都存在一条路径。可以有多个边连接同一对顶点。该图可以包含自循环,即。 e.将节点连接到自身的边。
顶点 $$$u$$$ 和 $$$v$$$ 之间的距离表示为 $$$\rho(u, v)$$$,等于 $$$u$$$ 和 $$$v$$$ 之间路径上的最小可能边数。图 $$$G$$$ 的直径定义为其某对顶点之间的最大可能距离。我们将其表示为$$$d(G)$$$。换句话说,$$$$$$d(G) = \max_{1 \le u, v \le n}{\rho(u, v)}.$$$$$$
Jack 计划连续对他的图表应用 $$$q$$$ 更新。每次更新都会向图表添加一条边。将恰好进行 $$$i$$$ 更新后的图表表示为 $$$G_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$$$,使得 $$$$$$\left\lceil \frac{d(G_i)}{2} \right\rceil \le a_i \le 2 \cdot d(G_i)$$$$$$ 对于每个 $$$i$$$。
黑客
你无法解决这个问题。
输入
输入的第一行包含三个整数 $$$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$$$ 更新中添加到图中的边连接的顶点的索引。
重要说明。出于测试目的,输入数据可能在提到的输入格式之后包含一些额外的行。检查员将使用这些来验证您的答案。它们不是测试数据的一部分,您不应该以任何方式使用它们,甚至可以省略读取它们。
输出
打印 $$$q + 1$$$ 正整数 $$$a_0, a_1, a_2, \ldots, 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), \ldots, d(G_q)$$$ 的正确序列是 $$$6, 6, 6, 3, 3, 3, 2, 2, 2$$$。
在第二个示例中,输入包含一个额外的行,您可以省略读取。它不是测试的一部分,将用于验证您的答案。第二个示例的输出包含 $$$d(G_i)$$$ 的正确值。