CF1804F.Approximate Diameter
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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 ρ(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.
输入格式
The first line of the input contains three integers n , m , and q ( 2≤n≤105 , n−1≤m≤105 , 0≤q≤105 ), 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 ui and vi ( 1≤ui,vi≤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 ui′ and vi′ ( 1≤ui′,vi′≤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 a0,a1,a2,…,aq . The i -th of these integers should differ from the diameter of graph Gi no more than twice.
输入输出样例
输入#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
说明/提示
In the first example, the correct sequence of d(G0),d(G1),d(G2),…,d(Gq) 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(Gi) .