本人有一个同学的优化后的暴力做法A了此题。本人据其思路码的代码如下：

#include<cstdio>
#include<set>
const int N = 500010;
using std::set;
set<int> s[N],s1[N],st1,st2,st3,st4,opt1[N],opt3[N];
int n,m,u,v,q,cd[N],rd[N],rdmx[N],t,cnt,edgecnt;
set<int>::iterator it,it1;
int main()
{
//	freopen("galaxy.in","r",stdin);
//	freopen("galaxy.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i = 1;i <= m;++i)
		scanf("%d%d",&u,&v),++cd[u],++edgecnt,++rd[v],s[v].insert(u);
	for (int i = 1;i <= n;++i)
		cnt += cd[i] == 1,rdmx[i] = rd[i];
	scanf("%d",&q);
	for (int i = 1;i <= q;++i)
	{
		scanf("%d%d",&t,&u);
		if (t == 1)
		{
			scanf("%d",&v),--edgecnt,--rd[v];
			if (opt3[v].find(u) != opt3[v].end())
				opt3[v].erase(u);
			else
				opt1[v].insert(u),st1.insert(v);
		}
		else if (t == 3)
		{
			scanf("%d",&v),++edgecnt,++rd[v];
			if (opt1[v].find(u) != opt1[v].end())
				opt1[v].erase(u);
			else
				opt3[v].insert(u),st3.insert(v);
		}
		else if (t == 2)
		{
			edgecnt -= rd[u],rd[u] = 0,opt1[u].clear(),opt3[u].clear();
			st1.erase(u),st3.erase(u),st4.erase(u),st2.insert(u);
		}
		else
		{
			edgecnt += rdmx[u]-rd[u],rd[u] = rdmx[u],opt1[u].clear(),opt3[u].clear();
			st1.erase(u),st2.erase(u),st3.erase(u),st4.insert(u);
		}
		if (edgecnt == n)
		{
			for (it = st2.begin(),u = *it;it != st2.end();++it,s[u].clear(),u = *it)
				for (it1 = s[u].begin(),v = *it1;it1 != s[u].end();++it1,v = *it1)
					s1[u].insert(v),--cd[v],cnt += (cd[v] == 1)-(cd[v] == 0);
			for (it = st4.begin(),u = *it;it != st4.end();++it,s1[u].clear(),u = *it)
				for (it1 = s1[u].begin(),v = *it1;it1 != s1[u].end();++it1,v = *it1)
					s[u].insert(v),++cd[v],cnt += (cd[v] == 1)-(cd[v] == 2);
			for (it = st1.begin(),u = *it;it != st1.end();++it,opt1[u].clear(),u = *it)
				for (it1 = opt1[u].begin(),v = *it1;it1 != opt1[u].end();++it1,v = *it1)
					s[u].erase(v),s1[u].insert(v),--cd[v],cnt += (cd[v] == 1)-(cd[v] == 0);
			for (it = st3.begin(),u = *it;it != st3.end();++it,opt3[u].clear(),u = *it)
				for (it1 = opt3[u].begin(),v = *it1;it1 != opt3[u].end();++it1,v = *it1)
					s1[u].erase(v),s[u].insert(v),++cd[v],cnt += (cd[v] == 1)-(cd[v] == 2);
			st1.clear(),st2.clear(),st3.clear(),st4.clear();
			puts(cnt == n?"YES":"NO");
		}
		else
			puts("NO");
	}
	return 0;
}

提交记录

然而这个做法的最坏时间复杂度为 $\Theta(nq\log n)$ 。可以被以下生成器产生的数据卡到此上界：

#include<cstdio>
int f[2][2] = {{1,2},{2,1}};
int main()
{
	freopen("galaxy.in","w",stdout);
	int n = 250001,m = 500000;
	printf("%d %d\n",n,m);
	for (int i = 3;i <= n;++i)
		printf("%d %d\n%d %d\n",i,1,i,2);
	printf("1 3\n2 3\n");
	int q = 500000-1;
	printf("%d\n",q);
	printf("2 1\n");
	for (int i = 1;i*2+1 <= q;++i)
		printf("4 %d\n2 %d\n",f[(i&1)^1][0],f[(i&1)^1][1]);
	return 0;
}