Description：

给出一个连通带权无向图,边有边权,要求支持 $q$ 个操作：

$1$ $x$ $y$ $d$ 在原图中加入一条 $x$ 到 $y$ 权值为 $b$ 的边。

$2$ $x$ $y$ 把图中 $x$ 到 $y$ 的边删掉

$3$ $x$ $y$ 表示询问 $x$ 到 $y$ 的异或最短路

保证任意操作后原图连通无重边自环且操作均合法

$1\leqslant n\leqslant 2\times 10^5$

Solution：

经典的线段树分治 $+$ 线性基，但是还是有一些要注意的，显然是把所有的环找出来加到线性基里，然后随便求出来一棵生成树用树上的路径在线性基中查一个最小异或值，这个生成树必须一边 $dfs$ 一边求，所以用带撤销的并查集维护，把非树边形成的环加到线性基里，可以证明只要把这些环加进去就足够了（虽然还有别的环）。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,q;

#define MAXN 200010

struct edges{int u,v,w;};

struct LB

{

	int d[31];

	LB(){memset(d,0,sizeof(d));}

	void insert(int x)

	{

		for(int i = 30;i >= 0;--i)

		{

			if(x & (1 << i))

			{

				if(d[i] == 0){d[i] = x;break;}

				else x ^= d[i];

			}

		}

		return;

	}

	int query(int x)

	{

		for(int i = 30;i >= 0;--i)if((x ^ d[i]) < x)x ^= d[i];

		return x;

	}

};

map<pair<int,int>,pair<int,int> > p;

int f[MAXN],g[MAXN],rnk[MAXN];

int find(int x){return (x == f[x] ? x : find(f[x]));}

int getf(int x){return (x == f[x] ? 0 : g[x] ^ getf(f[x]));}

int stack[MAXN << 1],top = 0;

void merge(int a,int b,int c)

{

	int p = find(a),q = find(b);

	int v = getf(a) ^ getf(b) ^ c;

	if(rnk[p] > rnk[q])swap(p,q);

	f[p] = q;g[p] = v;stack[++top] = p;

	if(rnk[p] == rnk[q])++rnk[q],stack[++top] = -q;

	return;

}

void reset(int pos)

{

	while(top > pos)

	{

		int v = stack[top];--top;

		if(v > 0){f[v] = v;g[v] = 0;}

		else --rnk[-v];

	}

	return;

}

struct node

{

	int lc,rc;

	vector<edges> v;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void add(int rt,int L,int R,edges k,int l,int r)

{

	if(L > R)return;

	if(L <= l && r <= R)

	{

		t[rt].v.push_back(k);

		return;

	}

	if(L <= mid)add(t[rt].lc,L,R,k,l,mid);

	if(R > mid)add(t[rt].rc,L,R,k,mid + 1,r);

	return;

}

int qx[MAXN],qy[MAXN];

void calc(int rt,int L,int R,int l,int r,LB s)

{

	int pos = top;

	for(vector<edges>::iterator it = t[rt].v.begin();it != t[rt].v.end();++it)

	{

		if(find(it -> u) != find(it -> v))merge(it -> u,it -> v,it -> w);

		else s.insert(getf(it -> u) ^ getf(it -> v) ^ it -> w);

	}

	if(l == r)

	{

		printf("%d\n",s.query(getf(qx[l]) ^ getf(qy[l])));

	}

	else

	{

		if(L <= mid)calc(t[rt].lc,L,R,l,mid,s);

		if(R > mid)calc(t[rt].rc,L,R,mid + 1,r,s);

	}

	reset(pos);

	return;

}

#define fi first

#define se second

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)f[i] = i;

	int x,y,d;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&x,&y,&d);

		if(x > y)swap(x,y);

		p[make_pair(x,y)] = make_pair(d,1);

	}

	scanf("%d",&q);

	build(root,1,q);

	int N = 0;

	int opt;

	for(int i = 1;i <= q;++i)

	{

		scanf("%d%d%d",&opt,&x,&y);

		if(opt == 1)

		{

			scanf("%d",&d);

			if(x > y)swap(x,y);

			p[make_pair(x,y)] = make_pair(d,N + 1);

		}

		if(opt == 2)

		{

			if(x > y)swap(x,y);

			pair<int,int> it = p.find(make_pair(x,y)) -> se;

			add(root,it.se,N,(edges){x,y,it.fi},1,q);

			p.erase(p.find(make_pair(x,y)));

		}

		if(opt == 3)

		{

			++N;

			qx[N] = x;qy[N] = y;

		}

	}

	for(map<pair<int,int>,pair<int,int> >::iterator it = p.begin();it != p.end();++it)

	{

		add(root,it -> se.se,N,(edges){it -> fi.fi,it -> fi.se,it -> se.fi},1,q);

	}

	LB s;

	calc(root,1,N,1,q,s);

	return 0;

}