记录编号	215586	评测结果	AAAAAAAAAAAAAA
题目名称	[WC 2006]水管局长数据加强版	最终得分	100
用户昵称	ppfish	是否通过	通过
代码语言	C++	运行时间	3.795 s
提交时间	2015-12-23 00:43:28	内存使用	51.78 MiB

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

template<class T>inline void Read(T &x)
{
    int f = 1;
    char t = getchar();
    while (t < '0' || t > '9') {
        if (t == '-') f = -1;
        t = getchar();
    }
    x = 0;
    while (t >= '0' && t <= '9') {
        x = x * 10 + t - '0';
        t = getchar();
    }
    x *= f;
}

template<class T>void print(T &x)
{
    static int q[15], r;
    r = 0;
    do {
        q[++r] = x % 10;
        x /= 10;
    } while (x);
    while (r) putchar('0' + q[r--]);
    putchar('\n');
}

const int maxn = 100005;
const int maxq = 100005;
const int maxm = 1000005;
const int inf = 0x3f3f3f3f;

struct edge {
    int u, v, w, id;
    bool ban;
    void read() { Read(u), Read(v), Read(w); if (u > v) swap(u, v); }
    bool operator < (const edge &rhs) const { return w < rhs.w; }
};

struct node {
    int c[2], fa, mx;
    bool rev;
    node() { c[0] = c[1] = fa = mx = rev = 0; }
} T[maxn + maxm];

int n, m, q;
edge e[maxm], opr[maxq];
int val[maxn + maxm], idx[maxq], fa[maxn];

#define Fa(x) T[T[x].fa]
#define Lc(x) T[T[x].c[0]]
#define Rc(x) T[T[x].c[1]]

bool cmp(edge a, edge b) { return a.u < b.u || (a.u == b.u && a.v < b.v); }

bool isroot(int x) { return x != Fa(x).c[0] && x != Fa(x).c[1]; }

int gmax(const int &a, const int &b) { return val[a] > val[b] ? a : b; }

void update(int x) { T[x].mx = gmax(x, gmax(Lc(x).mx, Rc(x).mx)); }

void setc(int x, int y, bool mark)
{
    if (y) T[y].c[mark] = x;
    if (x) T[x].fa = y;
}

void pushdown(int x)
{
    if (T[x].rev) {
        T[x].rev ^= 1, Lc(x).rev ^= 1, Rc(x).rev ^= 1;
        swap(T[x].c[0], T[x].c[1]);
    }
}

void linkup(int x)
{
    static int line[maxn + maxm], now;
    line[now = 1] = x;
    while (!isroot(x)) line[++now] = T[x].fa, x = T[x].fa;
    while (now) pushdown(line[now --]);
}

void rotate(int x)
{
    if (isroot(x)) return;
    int p = T[x].fa, mark = (x == Fa(x).c[1]);
    if (!isroot(p)) setc(x, T[p].fa, p == Fa(p).c[1]);
    else T[x].fa = T[p].fa;
    setc(T[x].c[mark ^ 1], p, mark);
    setc(p, x, mark ^ 1);
    update(p), update(x);
}

void splay(int x)
{
    linkup(x);
    while (!isroot(x)) {
        int p = T[x].fa;
        if (!isroot(p)) {
            if ((x == T[p].c[1]) ^ (p == Fa(p).c[1])) rotate(x);
            else rotate(p);
        }
        rotate(x);
    }
}

void access(int x)
{
    for (register int r = 0; x; r = x, x = T[x].fa) {
        splay(x);
        T[x].c[1] = r;
        update(x);
    }
}

void makeroot(int x)
{
    access(x);
    splay(x);
    T[x].rev ^= 1;
}

void cut(int x, int y)
{
    makeroot(x), access(y), splay(y);
    T[y].c[0] = T[x].fa = 0, update(y);
}

void link(int x, int y)
{
    makeroot(x);
    T[x].fa = y;
}

int findroot(int x)
{
    access(x), splay(x);
    while (T[x].c[0]) x = T[x].c[0];
    return x;
}

int query(int x, int y)
{
    makeroot(x), access(y), splay(y);
    return T[y].mx;
}

void input()
{
    Read(n), Read(m), Read(q);
    for (register int i = 1; i <= m; i++) e[i].read();
    for (register int i = 1; i <= q; i++) {
        Read(opr[i].w), Read(opr[i].u), Read(opr[i].v);
        if (opr[i].u > opr[i].v) swap(opr[i].u, opr[i].v);
    }
}

int find(int a, int b)
{
    int l = 1, r = m, mid, re;
    while (r >= l) {
        mid = (l + r) >> 1;
        if (a == e[mid].u && b == e[mid].v) { re = mid; break; }
        else if (e[mid].u < a || (e[mid].u == a && e[mid].v < b)) l = mid + 1;
        else r = mid - 1;
    }
    return re;
}

int findfa(int x) { if (fa[x] == x) return x; else return fa[x] = findfa(fa[x]); }

void merge(int x, int y) { x = findfa(x), y = findfa(y); if (x != y) fa[x] = y; }

void prepare()
{
    int cnt = 0;
    sort(e + 1, e + m + 1, cmp);
    for (register int i = 1; i <= n; i++) fa[i] = i, val[i] = -inf;
    for (register int i = 1; i <= m; i++) e[i].id = i;
    for (register int i = 1; i <= q; i++) {
        if (opr[i].w == 2) {
            idx[i] = find(opr[i].u, opr[i].v);
            e[idx[i]].ban = true;
        }
    }
    sort(e + 1, e + m + 1);
    for (register int i = 1; i <= m; i++) {
        if (!e[i].ban) {
            int x = e[i].u, y = e[i].v, z = e[i].w;
            if (findfa(x) != findfa(y)) {
                merge(x, y);
                link(n + e[i].id, x), link(n + e[i].id, y);
                val[n + e[i].id] = z;
                cnt ++;
            }
            if (cnt == n - 1) break;
        }
    }
    sort(e + 1, e + m + 1, cmp);
}

void solve()
{
    static int ans[maxq], ln = 0;
    register int now, x, y, z, re;
    for (register int i = q; i >= 1; i--) {
        if (opr[i].w == 1) {
            ans[++ln] = val[query(opr[i].u, opr[i].v)];
        } else {
            now = idx[i], x = e[now].u, y = e[now].v, z = e[now].w, re = query(x, y);
            if (val[re] > z) {
                cut(re, e[re - n].u);
                cut(re, e[re - n].v);
                link(n + idx[i], x), link(n + idx[i], y);
                val[n + idx[i]] = z;
            }
        }
    }
    for (register int i = ln; i >= 1; i--) print(ans[i]);
}

int main()
{
    //#ifndef ONLINE_JUDGE
    freopen("tube_strong.in", "r", stdin);
    freopen("tube_strong.out", "w", stdout);
    //#endif

    input();
    prepare();
    solve();

#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
#endif
    return 0;
}