A15826 | 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)}. $$ </p><p>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)$ .</p><p>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.

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.

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.