Solution

考虑对两种操作进行逆操作。

对于第一种操作，直接把图按连通块分成若干个联通子图。

对于第二种操作，考虑把图按照补图分成若干个联通子图。

如果两种操作都无法实施，那么失败。

如何模拟呢？对于第一种，暴力扫描是 $O(n+m)$ 的；对于第二种，考虑增量：增加节点时，计算该节点和之前已有的所有连通块相连的边数，如果和连通块大小不相等就合并。根据势能分析，这样做也是 $O(n+m)$ 的。

单次复杂度弄明白了，总体复杂度怎么样？

显然操作 $1$ 和 $2$ 是交替进行的，因此可以不考虑操作 $1$ 的复杂度（因为必定伴随一次复杂度几乎相同的操作 $2$）。每完成一次操作 $2$，$m$ 至少减去 $n-1$。考虑 $n$ 是递减的，因此操作最多进行 $O(\sqrt m)$ 层，复杂度为 $O((n+m)\sqrt m)$。

跑得飞快。

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e4+10;
int T,n,m,fa[MAXN],sze[MAXN],cnt[MAXN],ans;
vector<int> G[MAXN];
int find(int k) {return (fa[k]==k)?k:(fa[k]=find(fa[k]));}
void merge(int u,int v) {
	u=find(u),v=find(v);
	if(u==v) return ;
	if(sze[u]<sze[v]) swap(u,v);
	fa[v]=u,sze[u]+=sze[v];
	return ;	
}
vector<int> psl[MAXN];
int flg[MAXN];
void solve(vector<int> id) {
	if(id.size()==1) return ;	
	for(auto u:id) flg[u]=1;
	for(auto u:id) fa[u]=u,sze[u]=1,cnt[u]=0;
	for(auto u:id) for(auto v:G[u]) if(flg[v]) merge(u,v);
	for(auto u:id) flg[u]=0;
	int al=0;
	for(auto u:id) al+=(find(u)==u);
	if(al!=1) {
		for(auto u:id) psl[u].clear();
		for(auto u:id) psl[find(u)].push_back(u);
		for(auto u:id) if(find(u)==u) solve(psl[u]);
		return ;
	}
	for(auto u:id) flg[u]=1;
	for(auto u:id) fa[u]=u,sze[u]=1,cnt[u]=0;
	vector<int> bl;
	for(auto u:id) {
		vector<int> nbl;
		for(auto b:bl) cnt[b]=0;
		for(auto v:G[u]) if(flg[v]) cnt[find(v)]++;
		for(auto b:bl) if(cnt[b]!=sze[b]) merge(u,b);
		else nbl.push_back(b);
		nbl.push_back(find(u)),bl=nbl;	
	}
	for(auto u:id) flg[u]=0;
	if(bl.size()!=1) {
		for(auto u:id) psl[u].clear();
		for(auto u:id) psl[find(u)].push_back(u);
		for(auto u:id) if(find(u)==u) solve(psl[u]);
		return ;	
	}
	ans=1;
	return ;
}
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--) {
		vector<pair<int,int>> vc;
		cin>>n>>m,ans=0;
		ffor(i,1,m) {
			int u,v;
			cin>>u>>v;
			if(u>v) swap(u,v);
			G[v].push_back(u);
		}
		vector<int> al;
		ffor(i,1,n) al.push_back(i);
		solve(al);
		ffor(i,1,n) G[i].clear();
		if(!ans) cout<<"TAK\n";
		else cout<<"NIE\n";
	}
	return 0;
}