Alliance Formation in the S-Galaxy

In a distant S-Galaxy there are (n) planets labeled from (1) to (n). Initially, there are (m) bidirectional space tunnels connecting some pairs of planets such that each tunnel enables travel between its two endpoints. Some planets decide to form alliances but the primary condition is that the transportation network must support robust communication. In particular, if two planets belong to the same alliance then there must exist a circular route (i.e. two paths sharing no common tunnel) connecting these two planets. In other words, the planets in an alliance form a 2-edge-connected component of the graph. (p) new space tunnels will be constructed sequentially. After each new tunnel is built, it might merge different alliances. Your task is: when a new tunnel is completed, check whether the two planets connected by that tunnel are in the same alliance (i.e. lie in the same 2-edge-connected component). If they do, output the number of planets in that alliance; otherwise, output 0.


Note: A 2-edge-connected component in an undirected graph is a maximal set of vertices such that any two vertices in the set are connected by at least two edge-disjoint paths. This condition is equivalent to saying that no edge of the component is a bridge (an edge whose removal increases the number of connected components).

inputFormat

The first line contains three integers (n), (m), and (p) where (n) is the number of planets, (m) is the number of initial tunnels, and (p) is the number of new tunnels to be constructed.

The next (m) lines each contain two integers (u) and (v) ((1 \le u,v \le n)) representing a bidirectional tunnel between planet (u) and planet (v).

Each of the following (p) lines contains two integers (u) and (v) representing a new tunnel built between planet (u) and planet (v) in that order.

outputFormat

For each new tunnel (in the given order), output a single integer in a separate line. If the two planets connected by the new tunnel are in the same alliance (i.e. same 2-edge-connected component) after the tunnel is built, output the total number of planets in that alliance; otherwise, output 0.

sample

5 4 3
1 2
2 3
3 4
4 5
1 3
2 4
4 5

0
4
5