B'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 <= u, v <= 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 <= ft lceil frac{d(G_i)}{2} right rceil <= a_i <= 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 <= q n <= q 10^5 , n - 1 <= q m <= q 10^5 , 0 <= q q <= q 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 <= q u_i, v_i <= q n ), the indexes of the vertices connected by the i -th edge. Then follow q lines describing the updates. '...