记录编号	478872	评测结果	AAAAAAAAAAAAAAA
题目名称	[WC 2006]水管局长数据加强版	最终得分	100
用户昵称	Cooook	是否通过	通过
代码语言	C++	运行时间	6.197 s
提交时间	2017-12-14 21:13:22	内存使用	99.50 MiB

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

#define Debug printf("%d\n",__LINE__)
#define id(_) (_-null)
#define fi first
#define se second
#define mk std::make_pair

typedef std::pair<int,int> pii;

const int MAXN = 100005,MAXM = 2e6+5;
int n,m,Q,val[MAXM>>1],u[MAXM>>1],v[MAXM>>1],cnt,Ans[MAXM>>1],Query_time;


template <typename _t>
inline _t read(){
    _t x = 0, f = 1;
    char ch = getchar();
    for (; ch < '0' | ch > '9'; ch = getchar()) if (ch == '-') f = -f;
    for (; ch >= '0' & ch <= '9'; ch = getchar()) x = x * 10 + (ch ^ 48);
    return x * f;
}

struct edge{int u,v,w;}a[MAXM>>1];
struct Operation{int op,x,y;}op[(int)1e6+5];
struct node{
    node *ch[2],*f;
    int mx,val,tag,id,pos;
    inline void Maintain();
    inline void Push_down();
    inline void rev();
    inline void rotate();
    inline void Splay();
    inline bool dir();
    inline bool isrt();
}null[MAXM];

inline bool node::dir(){
    return f -> ch[1] == this;
}

inline bool node::isrt(){
    return f -> ch[0] != this && f -> ch[1] != this;
}

inline void node::rev(){
    if (this == null) return;
    std::swap(ch[0],ch[1]), tag ^= 1;
}

inline void node::rotate(){
    node *fa = f, *pa = fa -> f; int d = dir();
    if (!fa -> isrt()) pa -> ch[fa -> dir()] = this;
    if ((fa -> ch[d] = ch[d ^ 1]) != null) ch[d ^ 1] -> f = fa;
    fa -> f = this; this -> f = pa; ch[d ^ 1] = fa;
    fa -> Maintain(); Maintain();
}

inline void node::Splay(){
    Push_down();
    for (node *t = f; !isrt(); rotate(), t = f) 
        if (!t -> isrt()){
            t -> f -> Push_down(), t -> Push_down(), Push_down();
            if (t -> dir() == dir()) t -> rotate();
            else rotate();
        }
        else t -> Push_down(), Push_down();
}

inline void node::Push_down(){
    if (this == null) return;
    if (tag) tag ^= 1, ch[0] -> rev(), ch[1] -> rev();
}

inline void node::Maintain(){
    if (this == null) return;
    mx = std::max(std::max(ch[0] -> mx,ch[1] -> mx),val);
    if (mx == ch[0] -> mx) pos = ch[0] -> pos;
    else if (mx == ch[1] -> mx) pos = ch[1] -> pos;
    else if (mx == val) pos = id;
}

inline void Access(node *x){
    node *y = null;
    while (x != null)
        x -> Splay(),
        x -> ch[1] = y,
        x -> Maintain(),
        y = x, x = x -> f;
}

inline void Make_root(node *x){
    Access(x); x -> Splay(); x -> rev();
}

inline void Link(node *x,node *y){
    Make_root(x); x -> Splay(); x -> f = y;
}

inline void Cut(node *x,node *y){
    Make_root(x); Access(y); x -> Splay();
    x -> ch[1] = y -> f = null;
}

inline node* find(node *x){
    Access(x); x -> Splay(); x -> Push_down();
    while (x -> ch[0] != null)
        x = x -> ch[0], x -> Push_down();
    return x;
}

inline int Query(node *x,node *y){
    Make_root(x);
    Access(y);
    y -> Splay();
    return y -> pos;
}

inline void Add_Edge(node *x,node *y,node *z,int w){
    if (find(x) != find(y))
        return Link(x,z), Link(y,z), void();
    else {
        int id = Query(x,y);
        if (w < val[id-n]) Cut(&null[a[id-n].u],&null[id]),Cut(&null[a[id-n].v],&null[id]),Link(x,z),Link(y,z);
    }
}

std::map<pii,int> ma,Del;

int main(){
    freopen("tube_strong.in","r",stdin);
    freopen("tube_strong.out","w",stdout);
    n = read<int>(), m = read<int>(), Q = read<int>();
    for (int i = 0; i <= n + m; i++)
        null[i].ch[0] = null[i].ch[1] = null[i].f = null,
        null[i].tag = 0, null[i].id = i, null[i].mx = 0, null[i].pos = i;
    for (int i = 1; i <= m; i++){
        a[i].u = read<int>(),a[i].v = read<int>(),a[i].w = read<int>();
        null[i+n].mx = null[i+n].val = a[i].w; val[i] = a[i].w; 
        if (a[i].u > a[i].v) std::swap(a[i].u,a[i].v);
        ma[mk(a[i].u,a[i].v)] = i;
    }
    for (int i = 1; i <= Q; ++i){
        op[i].op = read<int>(),op[i].x = read<int>(), op[i].y = read<int>();
        if (op[i].x > op[i].y) std::swap(op[i].x,op[i].y);
        if (op[i].op == 2) Del[mk(op[i].x,op[i].y)] = ma[mk(op[i].x,op[i].y)], ma.erase(mk(op[i].x,op[i].y));
    }
    for (int i = 1; i <= m; i++)
        if (ma.count(mk(a[i].u,a[i].v)))
            Add_Edge(&null[a[i].u],&null[a[i].v],&null[n+i],a[i].w);
    for (int i = Q; i; --i){
        if (op[i].op == 1)
            Ans[++Query_time] = val[Query(&null[op[i].x],&null[op[i].y]) - n];
        else Add_Edge(&null[op[i].x],&null[op[i].y],&null[Del[mk(op[i].x,op[i].y)]+n],val[Del[mk(op[i].x,op[i].y)]]);
    }
    for (int i = Query_time; i; --i) printf("%d\n",Ans[i]);
    return 0;
}