Approximate Diameter
Contest: Nebius Welcome Round (Div. 1 + Div. 2)
Difficulty rating: 2700
Tags: binary search, divide and conquer, graphs, shortest paths

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 format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

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

Example input:
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

Example output:
10 6 5 6 2 4 2 2 1

Example 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

Example output:
7 5 4 4 4 3 3 3 3 3

Editorial:
Let's recall some definitions to start with.
• $$$\rho_G(u, v)$$$ is the length of the shortest path between vertices $$$u$$$ and $$$v$$$ in graph $$$G$$$.
• Define as $$$c_G(u)$$$ the maximum distance from vertex $$$u$$$ to some other vertex of graph $$$G$$$. $$$c_G(u) = \max_{v \in V(G)} \rho(u, v)$$$.
• $$$d(G) = \max_{u, v \in V(G)} \rho(u, v) = \max_{u \in V(G)} c_G(u)$$$ is called the diameter of graph $$$G$$$. It is the maximum distance between some pair of vertices of graph $$$G$$$.
• $$$r(G) = \min_{u \in V(G)} \max_{v \in V(G)} \rho(u, v) = \min_{u \in V(G)} c(u)$$$ is called the radius of graph $$$G$$$. It is the minimum possible distance from one vertex of the graph to the farthest from it vertex of this graph.
The key inequality we will use for this problem solution is the following. Let $$$v$$$ be arbitrary vertex of graph $$$G$$$.
$$$$$$\frac{d(G)}{2} \leq r(G) \leq c_G(v) \leq d(G) \leq 2 \cdot r(G) \leq 2 \cdot c_G(v) \leq 2 \cdot d(G)$$$$$$
• $$$r(G) \leq c_G(v) \leq d(G)$$$ by definition.
• $$$d(G) \leq 2 \cdot r(G)$$$ because of triangle inequality.
• All other inequalities are derived from the first two items.
The good thing is that we can compute $$$c_G(v)$$$ in linear time using BFS algorithm. Now we can solve the problem in $$$O(q \cdot (n + m + q))$$$ time. It is important to note that the task tolerates errors both ways, so any value between $$$c_{G_i}(v)$$$ and $$$2 \cdot c_{G_i}(v)$$$ will be a correct approximation of $$$d(G_i)$$$.
The next key observation is that the sequence of $$$d_i(G)$$$ is non-increasing. If $$$i < j$$$ and $$$c_{G_i}(v) \leq 2 \cdot c_{G_j}(v)$$$ we can use $$$2 \cdot c_{G_j}(v)$$$ as an approximation for $$$d(G_{i + 1}), d(G_{i + 2}), \ldots, d(G_{j - 1})$$$.
Using the idea above we can do one of the following.
• Having the correct value of $$$c_{G_i}(v)$$$ we can use the binary search to find the maximum $$$j$$$ such that $$$c_{G_i}(v) \leq 2 \cdot c_{G_j}(v)$$$ in $$$\log{q}$$$ iterations.
• Use divide&conquer with the stop condition $$$c_{G_l}(v) \leq 2 \cdot c_{G_r}(v)$$$. That would actually work a way more faster (up to five times) as it re-uses the information very efficiently.
Thus, we have a solion that runs BFS no more than $$$\log{n} \cdot \log{q}$$$ times. The overall complexity is $$$O(\log{n} \cdot \log{q} \cdot (n + m + q))$$$.
How did we get the correct answers for the checker? We precomputed them using the power of distributed computing. We are a cloud technology company after all!
Bonus question, can you guess the total number of cpu-days we have used to compute all the answers? Post you version in the comments!