310247: CF1804F. Approximate Diameter

F. Approximate Diametertime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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.

Input

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.

Output

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.

ExamplesInput

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

Output

10 6 5 6 2 4 2 2 1

Input

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

Output

7 5 4 4 4 3 3 3 3 3

Note

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)$.

题目大意：
杰克有一个包含n个顶点和m条边的图。所有边都是双向的，长度为1。该图是连通的，即任意两个顶点之间都存在路径。同一对顶点之间可以有多于一条边连接。图中可能包含自环，即连接顶点到自身的边。

顶点u和v之间的距离表示为ρ(u, v)，等于u和v之间路径上边的最小可能数量。图G的直径定义为图中任意一对顶点之间的最大可能距离。我们将其表示为d(G)。换句话说，d(G) = max_{1 ≤ u, v ≤ n} ρ(u, v)。

杰克打算对他的图连续进行q次更新。每次更新都会向图中添加一条边。用Gi表示进行恰好i次更新后的图。杰克想要计算q + 1个值d(G0), d(G1), d(G2), …, d(Gq)。

然而，杰克怀疑找到q + 1个图的确切直径可能是一个困难的任务，所以他对近似答案感到满意，这些答案与正确答案的偏差不超过两倍。正式地说，杰克想要找到一个正整数序列a0, a1, a2, …, aq，使得对于每个i，满足以下条件：⌈d(Gi)/2⌉ ≤ ai ≤ 2 * d(Gi)。

输入输出数据格式：
输入：
第一行包含三个整数n、m和q（2 ≤ n ≤ 10^5，n - 1 ≤ m ≤ 10^5，0 ≤ q ≤ 10^5），分别表示给定图的顶点数、边数和更新数。

接下来m行描述图的初始边。第i行包含两个整数ui和vi（1 ≤ ui, vi ≤ n），表示第i条边连接的顶点的索引。

接下来q行描述更新。第i行包含两个整数u'_i和v'_i（1 ≤ u'_i, v'_i ≤ n），表示在图中的第i次更新中添加的边的顶点索引。

输出：
打印一个包含q + 1个正整数的序列a0, a1, a2, …, aq。序列中的第i个数应与图Gi的直径的偏差不超过两倍。题目大意： 杰克有一个包含n个顶点和m条边的图。所有边都是双向的，长度为1。该图是连通的，即任意两个顶点之间都存在路径。同一对顶点之间可以有多于一条边连接。图中可能包含自环，即连接顶点到自身的边。 顶点u和v之间的距离表示为ρ(u, v)，等于u和v之间路径上边的最小可能数量。图G的直径定义为图中任意一对顶点之间的最大可能距离。我们将其表示为d(G)。换句话说，d(G) = max_{1 ≤ u, v ≤ n} ρ(u, v)。 杰克打算对他的图连续进行q次更新。每次更新都会向图中添加一条边。用Gi表示进行恰好i次更新后的图。杰克想要计算q + 1个值d(G0), d(G1), d(G2), …, d(Gq)。 然而，杰克怀疑找到q + 1个图的确切直径可能是一个困难的任务，所以他对近似答案感到满意，这些答案与正确答案的偏差不超过两倍。正式地说，杰克想要找到一个正整数序列a0, a1, a2, …, aq，使得对于每个i，满足以下条件：⌈d(Gi)/2⌉ ≤ ai ≤ 2 * d(Gi)。 输入输出数据格式： 输入： 第一行包含三个整数n、m和q（2 ≤ n ≤ 10^5，n - 1 ≤ m ≤ 10^5，0 ≤ q ≤ 10^5），分别表示给定图的顶点数、边数和更新数。 接下来m行描述图的初始边。第i行包含两个整数ui和vi（1 ≤ ui, vi ≤ n），表示第i条边连接的顶点的索引。 接下来q行描述更新。第i行包含两个整数u'_i和v'_i（1 ≤ u'_i, v'_i ≤ n），表示在图中的第i次更新中添加的边的顶点索引。 输出： 打印一个包含q + 1个正整数的序列a0, a1, a2, …, aq。序列中的第i个数应与图Gi的直径的偏差不超过两倍。