题目链接

C. Civilization

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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.

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, 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:

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

Output

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

Sample test(s)

input

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

output

4

**思路：先计算出各个连通分量的最长的路径（两次dfs）， 合并的时候，按秩合并，同时更新最长路。
Accepted Code:
**

/*************************************************************************
> File Name: E.cpp
> Author: Stomach_ache
> Mail: sudaweitong@gmail.com
> Created Time: 2014年08月09日 星期六 08时16分23秒
> Propose:
************************************************************************/

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

const int maxn = ;
int n, m, q;
int d[maxn], p[maxn], rank[maxn];
int x, w, best;
vector g[maxn];

int getFa(int x) {
return x != p[x] ? p[x] = getFa(p[x]) : x;
}

void dfs(int u, int fa, int high) {
p[u] = x;
if (high > best) best = high, w = u;
for (int i = ; i < (int)g[u].size(); i++) if (g[u][i] != fa)
dfs(g[u][i], u, high + );
}

void unite(int x, int y) {
if (x == y) return ;
if (rank[x] >= rank[y]) {
p[y] = x;
d[x] = max(max(d[x], d[y]), (d[x]+)/+(d[y]+)/+);
if (rank[x] == rank[y]) rank[x]++;
} else {
p[x] = y;
d[y] = max(max(d[x], d[y]), (d[x]+)/+(d[y]+)/+);
}
}

int main(void) {
scanf("%d %d %d", &n, &m, &q);
for (int i = ; i < m; i++) {
int from, to;
scanf("%d %d", &from, &to);
g[from].push_back(to);
g[to].push_back(from);
}
for (x = ; x <= n; x++) if (!p[x]) {
best = -; dfs(x, , );
best = -, dfs(w, , );
d[x] = best;
}
while (q--) {
int t;
scanf("%d %d", &t, &x);
if (t == ) {
printf("%d\n", d[getFa(x)]);
} else {
int y;
scanf("%d", &y);
unite(getFa(x), getFa(y));
}
}
return ;
}