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

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.

N/A

N/A

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