|Codeforces Round #260 (Div. 1)|
Andrew plays a game called "Civilization". Dima helps him.
The game has n cities and m bidirectional roads. The cities are numbered from 1 to n. Between any pair of cities there either is a single (unique) path, or there is no path at all. A path is such a sequence of distinct cities v 1, v 2, ..., v k, that there is a road between any contiguous cities v i and v i + 1 (1 ≤ i < k). The length of the described path equals to (k - 1). We assume that two cities lie in the same region if and only if, there is a path connecting these two cities.
During the game events of two types take place:
Dima finds it hard to execute Andrew's queries, so he asks you to help him. Help Dima.
The first line contains three integers n, m, q (1 ≤ n ≤ 3·105; 0 ≤ m < n; 1 ≤ q ≤ 3·105) — the number of cities, the number of the roads we already have and the number of queries, correspondingly.
Each of the following m lines contains two integers, a i and b i ( a i ≠ b i; 1 ≤ a i, b i ≤ n). These numbers represent the road between cities a i and b i. There can be at most one road between two cities.
Each of the following q lines contains one of the two events in the following format:
For each event of the first type print the answer on a separate line.
6 0 6
2 1 2
2 3 4
2 5 6
2 3 2
2 5 3