rt，WA on #1000 ~ #40000 行，$n \le 1000$ 过 $500$ 组拍

#include <bits/stdc++.h>
using namespace std;

inline void train() {
	   ios::sync_with_stdio(false);
	   cin.tie(0);
	   cout.tie(0);
}

inline int maxi(int a, int b) {
	return a > b ? a : b;
}

inline int mini(int a, int b) {
	return a < b ? a : b;
}

constexpr int N = 5e5+4, LN = 800004*4, M = 5e5+4;

vector<int> tree[N];

struct edge {
	int to, id;
	edge() {
		
	}
	edge(int to) : to(to) {
		
	}
	edge(int to, int id) : to(to), id(id) {
		
	}
};

priority_queue<edge> pq;
bool operator < (const edge &a, const edge &b) {
	return a.id < b.id;
}

vector<edge> graph[N], gentree[N];
int n, m, q, tid, father[N], ax[M], bx[M], save[M], depth[N], enable_when[N], target[N];
int cover[N], fas[N][20];
char otype[N];
int us[N], vs[N];
bool ans[N];
bool vis[N];


struct dset {
	dset() {
		
	}
	
	int fa[N], sz[N];

	inline void init(const int& n) {
		for (int i = 1; i <= n; i++) {
			fa[i] = i;
			sz[i] = 1;
		}
	}
	int query(const int& x) {
		return x == fa[x] ? x : fa[x] = query(fa[x]);
	}
	
	inline void merge(const int& a, const int& b) {
		int qa = query(a), qb = query(b);
		if (qa == qb) return;
		if (sz[qa] < sz[qb]) swap(qa, qb);
		fa[qb] = qa;
		sz[qa] += sz[qb];
	}
};

dset tarjan, complete, gens;


void dfs(int cur, int fa) {
//	cerr << fa << " -> " << cur << endl;
	depth[cur] = depth[fa] + 1;
	father[cur] = fa;
	for (auto &i : tree[cur]) {
		if (i == fa) continue;
		dfs(i, cur);
	}
}

int lca(int a, int b) {
	if (depth[a] < depth[b]) swap(a, b);
	int diff = depth[a] - depth[b];
	for (int i = 1<<19, bs = 19; i >= 1; i >>= 1, bs--) {
		if (diff & i) a = fas[a][bs];
	}
	if (a == b) return a;
	while (father[a] != father[b]) {
		int step = 19;
		for (; step >= 0 && fas[a][step] == fas[b][step]; step--);
		if (step < 0) return father[a];
		a = fas[a][step];
		b = fas[b][step];
	}
	return father[a];
}

void icover(int a, int l, int s) {
	int x = a;
	while (depth[a] > depth[l]) {
		cover[a]++;
		if (cover[a] > 1) tarjan.merge(a, l);
//		cerr << "Executed to " << a << ", covering " << cover[a] << endl;
		a = father[target[a]];
	}
	while (depth[x] > depth[l]) {
		int tmp = father[target[x]];
		if (cover[x] > 1) target[x] = a;
		x = tmp;
	}
}

void covering(int a, int b) {
	int l = lca(a, b);
//	cerr << "Covering " << a << " and " << b << ", LCA = " << l << endl;
	icover(a, l, a);
//	cerr << "===\n";
	icover(b, l, a);
//	cerr << endl;
}

set<pair<int, int> > edges;
map<pair<int, int>, int> ids;


void dfs1(int cur, int fa) {
	vis[cur] = true;
	for (auto &i : graph[cur]) {
		pq.push(edge(i.id, save[i.id]));
		if (vis[i.to]) continue;
		dfs1(i.to, cur);
	}
}

int main() {

	train();
	
	cin>>n>>m>>q;
	tarjan.init(n); complete.init(n); gens.init(n);
	for (int i = 1; i <= m; i++) {
		cin>>ax[i]>>bx[i];
		int a = ax[i], b = bx[i];
		graph[ax[i]].push_back(edge(bx[i], i));
		graph[bx[i]].push_back(edge(ax[i], i));
		auto ap = make_pair(mini(a,b),maxi(a,b));
		edges.insert(ap);
		save[i] = q+1;
		ids[ap] = i;
		complete.merge(ax[i], bx[i]);
	}
	for (int i = 1; i <= q; i++) {
		cin>>otype[i]>>us[i]>>vs[i];
		int a = us[i], b = vs[i];
		if (otype[i] == 'Z') {
			auto ap = make_pair(mini(a,b),maxi(a,b));
			edges.erase(ap);
			save[ids[ap]] = i;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (complete.query(i) == i) {
			// Generate a tree:
			dfs1(i, i);
//			cerr << "Construct tree for " << i << endl;
			int cnt = 0;
			while ((cnt <= complete.sz[i]) && (!pq.empty())) {
				edge pt = pq.top();
				pq.pop();
				if (gens.query(ax[pt.to]) == gens.query(bx[pt.to])) continue;
				tree[ax[pt.to]].emplace_back(bx[pt.to]);
				tree[bx[pt.to]].emplace_back(ax[pt.to]);
//				cerr << ax[pt.to] << " <-> " << bx[pt.to] << endl;
				cnt++;
				gens.merge(ax[pt.to], bx[pt.to]);
			}
			while (!pq.empty()) pq.pop();
			dfs(i, i);
		}
		target[i] = i;
	}
	for (int i = 1; i <= n; i++) {
		target[i] = i;
		fas[i][0] = father[i];
	}
	for (int step = 1; step < 20; step++) {
		for (int i = 1; i <= n; i++) fas[i][step] = fas[fas[i][step-1]][step-1]; 
	}
	for (auto &i : edges) covering(i.first, i.second);
	for (int i = q; i >= 1; i--) {
		switch (otype[i]) {
			case 'Z':
				// Do the cover
				covering(us[i], vs[i]);
				break;
			case 'P':
				ans[i] = (tarjan.query(us[i]) == tarjan.query(vs[i]));
				break;
		}
	}
	for (int i = 1; i <= q; i++) {
		if (otype[i] == 'P') {
			if (ans[i]) cout<<"TAK\n";
			else cout<<"NIE\n";
		}
	}
	
	cout<<flush;

	return 0;
}