#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
long long max(long long a, long long b) {
  if (a > b)
    return a;
  else
    return b;
}
long long min(long long a, long long b) {
  if (a > b)
    return b;
  else
    return a;
}
long long gcd(long long a, long long b) { return (b == 0) ? a : gcd(b, a % b); }
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long normalize(long long x, long long mod) {
  x %= mod;
  if (x < 0) x += mod;
  return x;
}
long long dx[4] = {0, 0, 1, -1};
long long dy[4] = {1, -1, 0, 0};
string abc = "abcdefghijklmnopqrstuvwxyz";
const double PI = acosl(-1);
const long long mod = 1000 * 1000 * 1000 + 7;
const long long inf = 1e18 + 5;
inline long long add(long long a, long long b, long long p = mod) {
  long long c = a + b;
  if (c >= p) c -= p;
  return c;
}
inline long long sub(long long a, long long b, long long p = mod) {
  long long c = a - b;
  if (c < 0) c += p;
  return c;
}
inline long long mul(long long a, long long b, long long p = mod) {
  return (a * 1LL * b) % p;
}
long long floor1(long long n, long long k) {
  if (n % k == 0 || n >= 0) return n / k;
  return (n / k) - 1;
}
long long ceil1(long long n, long long k) { return floor1(n + k - 1, k); }
long long powm(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) res = (res * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return res;
}
const long long N = 3e5 + 5;
long long n, m, q;
vector<long long> g[N];
long long vis[N];
long long dia[N];
long long parent[N], size1[N];
void make_set(long long v) {
  parent[v] = v;
  size1[v] = 1;
}
long long find_set(long long v) {
  if (v == parent[v]) return v;
  return parent[v] = find_set(parent[v]);
}
void union_sets(long long a, long long b) {
  a = find_set(a);
  b = find_set(b);
  if (a != b) {
    if (size1[a] < size1[b]) swap(a, b);
    parent[b] = a;
    dia[a] = max(dia[a], max(dia[b], ceil1(dia[a], 2) + ceil1(dia[b], 2) + 1));
    size1[a] += size1[b];
  }
}
long long dist = 0, node = 0;
void dfs(long long x, long long par, long long curd) {
  vis[x] = 1;
  if (curd > dist) {
    dist = curd;
    node = x;
  }
  for (auto &it : g[x]) {
    if (it == par) continue;
    dfs(it, x, curd + 1);
  }
}
long long diam(long long x) {
  node = x;
  dist = 0;
  dfs(node, node, 0);
  dfs(node, node, 0);
  return dist;
}
void solve() {
  cin >> n >> m >> q;
  for (long long i = (1); i < (n + 1); ++i) make_set(i);
  for (long long i = (1); i < (m + 1); ++i) {
    long long u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
    union_sets(u, v);
  }
  for (long long i = (1); i < (n + 1); ++i) {
    if (vis[i] == 0) {
      dist = 0;
      dia[find_set(i)] = diam(i);
    }
  }
  while (q--) {
    long long t;
    cin >> t;
    if (t == 1) {
      long long x;
      cin >> x;
      cout << dia[find_set(x)] << "\n";
    } else {
      long long x, y;
      cin >> x >> y;
      union_sets(x, y);
    }
  }
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(10);
  long long t = 1;
  for (long long i = (1); i < (t + 1); ++i) {
    solve();
  }
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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 v1, v2, ..., vk, that there is a road between any contiguous cities vi and vi + 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:

  1. Andrew asks Dima about the length of the longest path in the region where city x lies. 
  2. Andrew asks Dima to merge the region where city x lies with the region where city y lies. If the cities lie in the same region, then no merging is needed. Otherwise, you need to merge the regions as follows: choose a city from the first region, a city from the second region and connect them by a road so as to minimize the length of the longest path in the resulting region. If there are multiple ways to do so, you are allowed to choose any of them. 



Dima finds it hard to execute Andrew's queries, so he asks you to help him. Help Dima.

Input

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, ai and bi (ai ≠ bi; 1 ≤ ai, bi ≤ n). These numbers represent the road between cities ai and bi. 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:

  * 1 xi. It is the request Andrew gives to Dima to find the length of the maximum path in the region that contains city xi (1 ≤ xi ≤ n). 
  * 2 xi yi. It is the request Andrew gives to Dima to merge the region that contains city xi and the region that contains city yi (1 ≤ xi, yi ≤ n). Note, that xi can be equal to yi. 

Output

For each event of the first type print the answer on a separate line.

Examples

Input

6 0 6
2 1 2
2 3 4
2 5 6
2 3 2
2 5 3
1 1


Output

4

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
long long max(long long a, long long b) {
  if (a > b)
    return a;
  else
    return b;
}
long long min(long long a, long long b) {
  if (a > b)
    return b;
  else
    return a;
}
long long gcd(long long a, long long b) { return (b == 0) ? a : gcd(b, a % b); }
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long normalize(long long x, long long mod) {
  x %= mod;
  if (x < 0) x += mod;
  return x;
}
long long dx[4] = {0, 0, 1, -1};
long long dy[4] = {1, -1, 0, 0};
string abc = "abcdefghijklmnopqrstuvwxyz";
const double PI = acosl(-1);
const long long mod = 1000 * 1000 * 1000 + 7;
const long long inf = 1e18 + 5;
inline long long add(long long a, long long b, long long p = mod) {
  long long c = a + b;
  if (c >= p) c -= p;
  return c;
}
inline long long sub(long long a, long long b, long long p = mod) {
  long long c = a - b;
  if (c < 0) c += p;
  return c;
}
inline long long mul(long long a, long long b, long long p = mod) {
  return (a * 1LL * b) % p;
}
long long floor1(long long n, long long k) {
  if (n % k == 0 || n >= 0) return n / k;
  return (n / k) - 1;
}
long long ceil1(long long n, long long k) { return floor1(n + k - 1, k); }
long long powm(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) res = (res * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return res;
}
const long long N = 3e5 + 5;
long long n, m, q;
vector<long long> g[N];
long long vis[N];
long long dia[N];
long long parent[N], size1[N];
void make_set(long long v) {
  parent[v] = v;
  size1[v] = 1;
}
long long find_set(long long v) {
  if (v == parent[v]) return v;
  return parent[v] = find_set(parent[v]);
}
void union_sets(long long a, long long b) {
  a = find_set(a);
  b = find_set(b);
  if (a != b) {
    if (size1[a] < size1[b]) swap(a, b);
    parent[b] = a;
    dia[a] = max(dia[a], max(dia[b], ceil1(dia[a], 2) + ceil1(dia[b], 2) + 1));
    size1[a] += size1[b];
  }
}
long long dist = 0, node = 0;
void dfs(long long x, long long par, long long curd) {
  vis[x] = 1;
  if (curd > dist) {
    dist = curd;
    node = x;
  }
  for (auto &it : g[x]) {
    if (it == par) continue;
    dfs(it, x, curd + 1);
  }
}
long long diam(long long x) {
  node = x;
  dist = 0;
  dfs(node, node, 0);
  dfs(node, node, 0);
  return dist;
}
void solve() {
  cin >> n >> m >> q;
  for (long long i = (1); i < (n + 1); ++i) make_set(i);
  for (long long i = (1); i < (m + 1); ++i) {
    long long u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
    union_sets(u, v);
  }
  for (long long i = (1); i < (n + 1); ++i) {
    if (vis[i] == 0) {
      dist = 0;
      dia[find_set(i)] = diam(i);
    }
  }
  while (q--) {
    long long t;
    cin >> t;
    if (t == 1) {
      long long x;
      cin >> x;
      cout << dia[find_set(x)] << "\n";
    } else {
      long long x, y;
      cin >> x >> y;
      union_sets(x, y);
    }
  }
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(10);
  long long t = 1;
  for (long long i = (1); i < (t + 1); ++i) {
    solve();
  }
  return 0;
}

```