← 返回题目列表

Codeforces · 1804/F

F. 大约直径

中文机器翻译题面 查看原题

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)$$$ 的正确值。