boj8452.cpp

#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define cr(v, n) (v).clear(), (v).resize(n);

namespace EvenShiloach {
vector<list<int>> inlist, gph;
vector<array<list<int>::iterator, 2>> ptr;
vector<list<int>::iterator> par;
vector<int> dist, vis;
vector<pi> edges;
void init(int n, int m, int s, vector<pi> e) {
	cr(gph, n);
	cr(inlist, n);
	cr(ptr, m);
	cr(dist, n);
	cr(vis, n);
	cr(par, n);
	edges = e;
	fill(all(dist), 1e9);
	for (int i = 0; i < m; i++) {
		auto [u, v] = edges[i];
		ptr[i][0] = gph[u].insert(gph[u].end(), v);
		ptr[i][1] = inlist[v].insert(inlist[v].end(), u);
	}
	queue<int> que;
	que.push(s);
	dist[s] = 0;
	while (sz(que)) {
		int x = que.front();
		que.pop();
		for (auto &y : gph[x]) {
			if (dist[y] > dist[x] + 1) {
				que.push(y);
				dist[y] = dist[x] + 1;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		if (dist[i] > 0 && dist[i] < 1e8) {
			for (auto it = inlist[i].begin(); it != inlist[i].end(); it++) {
				if (dist[*it] == dist[i] - 1) {
					par[i] = it;
					break;
				}
			}
		}
	}
}

void erase(int i) {
	auto [u, v] = edges[i];
	if (ptr[i][1] != par[v]) {
		gph[edges[i][0]].erase(ptr[i][0]);
		inlist[edges[i][1]].erase(ptr[i][1]);
		return;
	}
	gph[u].erase(ptr[i][0]);
	par[v] = inlist[v].erase(ptr[i][1]);

	vector<int> redoList = {(int)v};
	vector<int> nextList;
	while (sz(redoList)) {
		nextList.clear();
		for (auto &v : redoList) {
			vis[v] = 0;
			while (par[v] != inlist[v].end()) {
				if (dist[*par[v]] == dist[v] - 1) {
					break;
				} else
					par[v]++;
			}
			if (par[v] == inlist[v].end()) {
				vis[v] = 1;
				nextList.push_back(v);
				par[v] = inlist[v].begin();
			}
		}

		bool disc = 0;
		redoList.clear();
		for (auto &w : nextList) {
			dist[w]++;
			if (dist[w] >= sz(gph))
				disc = 1;
			for (auto &z : gph[w]) {
				if (!vis[z] && dist[z] > 0 && *par[z] == w) {
					redoList.push_back(z);
					vis[z] = 1;
				}
			}
			redoList.push_back(w);
		}
		if (disc) {
			for (auto &w : redoList)
				dist[w] = 1e9;
			redoList.clear();
		}
	}
}
int query(int p) { return dist[p]; }
} // namespace EvenShiloach

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	vector<pi> edges(m);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		edges[i] = pi{u - 1, v - 1};
	}
	EvenShiloach::init(n, m, 0, edges);
	while (q--) {
		char c;
		int p;
		cin >> c >> p;
		if (c == 'U')
			EvenShiloach::erase(p - 1);
		else {
			int ans = EvenShiloach::query(p - 1);
			if (ans > 1e8)
				ans = -1;
			cout << ans << "\n";
		}
	}
}