问候

失礼了，没有问候。

析

思路概要

有显而然之的思路。

::::success[可能并不是这样显然]

大小为 1 的集合是合法的。

从全局往下，维护数次充分的分治。

如果我们废过，就立马停止这次递归。

一次充分的分治是指对当前集合进行一个划分，使得各个子集都可以通过操作一合并起来，而且各个子集都不能分为两个合法子集。而后对当前集合进行一个划分，使得各个子集都可以通过操作二合并起来，而且各个子集都不能分为两个合法子集。若第一遍和第二遍均只划分成了一个子集，就说明我们废了。

如果我们没有废，然后对每一个子集递归处理。

我们一直没有废，全局就一定是合法的。

::::

证明思路

先说答案的正确性。即充分的分治唯一。

::::success[为啥子我不明白]

以操作一为例。反证。例如有三个不交集合 $A$，$B$，$C$，满足 $AB$ 与 $C$ 为充分的分治，$CB$ 与 $A$ 亦为充分的分治。

即 $AB$ 与 $C$ 无边，$CB$ 与 $A$ 亦无边。也就是说三个集合两两无边。真正充分的分治是 $A$ 与 $B$ 与 $C$。与题设不符。

其余的充分的分治不唯一的情况也是大同小异，只不过是链式的，同样的证伪方法。

::::

时间复杂度分析

再说时间的正确性。

::::success[敲黑板（画星星）]

:::info[析 1] 第一种操作的分治是说，对于原图的连通块，我们会把它们一个一个地划出来。显然是 $O (curn + curm)$ 的。 ::: :::info[析 2] 第二种操作的分治是说，对于补图的连通块，我们会把它们一个一个地划出来。考虑那些新增一个点后在原图中连边不满的连通块，肯定和这个点合并。

我们不停地新增点。用一条原图中新增点与固有块连接的任意一条边来支付这一代价：新增点与该固有块在原图中连边恰满。

我们用并查集至多 $n - 1$ 次合并中的一次来支付这一代价：新增点与该固有块在原图中连边不满。 :::

然后是 $O (curn + curm)$ 的。

但是分治次数炸炸炸，总时间也炸炸炸。

考虑使用中庸平衡的思路。

注意到 $curn \ge \sqrt {m}$。不然你这图好稠密。不用重边我画不出来。

如果只用操作二分成了一条链亦减少了 $curn - 1$ 条边（以后分治不必再考虑），其余的减少的边只可能愈益多了呀！

分治次数 $O (\sqrt {m})$。 ::::

码

::::info[Code.]

#include<bits/stdc++.h>
#define int long long
#define y1 qht_yjx
#define hash ZhaoAk
#define maxn 10005
#define endl "\n"
#define nullptr 0
#define I ios::sync_with_stdio (nullptr);
#define AK cin.tie (nullptr);
#define CSP cout.tie (nullptr);


using namespace std;


int n ,m ,flag ,cnt[maxn];


struct BCJ
{
    int fa[maxn] ,siz[maxn];

    void init (vector <int> vec)
    {
        for (int x : vec)
            fa[x] = x ,siz[x] = 1 ,cnt[x] = 0;
        return ;
    }

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

    void merge (int x ,int y)
    {
        int fx = find (x) ,fy = find (y);
        if (fx == fy)
            return ;
        if (siz[fx] < siz[fy])
            swap (fx ,fy);
        siz[fx] += siz[fy];
        fa[fy] = fx;
        // cnt[fx] += cnt[fy];
        return ;
    }

} s;


bool bel[maxn];


vector <int> vec[maxn];


void adde (int u ,int v)
{
    if (u < v)
        swap (u ,v);
    vec[u].push_back (v);
    return ;
}


void brkdwn (vector <int> v)
{
    if (flag == 1)
        return ;
    if (v.size () <= 1)
        return ;
    
    s.init (v);
    for (int x : v)
        bel[x] = 1;
    for (int x : v)
        for (int y : vec[x])
            if (bel[y])
                s.merge (x ,y);
    for (int x : v)
        bel[x] = 0;
    
    int block_num = 0;
    for (int x : v)
        block_num += (int) (s.fa[x] == x);
    if (block_num > 1)
    {
        unordered_map <int ,vector <int> > mp;
        for (int x : v)
            mp[s.find (x)].push_back (x);
        for (int x : v)
        {
            if (s.find (x) == x)
                brkdwn (mp[x]);
        }
        return ;
    }
    
    s.init (v);
    for (int i = 1 ;i <= n ;i ++)
        bel[i] = 0;
    for (int x : v)
        bel[x] = 1;
    for (int x : v)
        cnt[x] = 0;
    vector <int> tar;
    for (int x : v)
    {
        vector <int> cur;
        for (int y : tar)
            cnt[y] = 0;
        for (int y : vec[x])
            if (bel[y])
                cnt[s.find (y)] ++;
        for (int y : tar)
        {
            if (cnt[y] != s.siz[y])
                s.merge (x ,y);
            else
                cur.push_back (y);
        }
        cur.push_back (s.find (x));
        tar = cur;
    }
    for (int x : v)
        bel[x] = 0;
    
    block_num = 0;
    for (int x : v)
        block_num += (int) (s.fa[x] == x);
    if (block_num > 1)
    {
        unordered_map <int ,vector <int> > mp;
        for (int x : v)
            mp[s.find (x)].push_back (x);
        for (int x : v)
        {
            if (x == s.find (x))
                brkdwn (mp[x]);
        }
        return ;
    }
    
    flag = 1;
    
    return ;
}


void Gogogo ()
{
    cin >> n >> m;
    for (int i = 1 ;i <= n ;i ++)
        vec[i].clear () ,bel[i] = 1;
    for (int i = 1 ;i <= m ;i ++)
    {
        int u ,v;
        cin >> u >> v;
        adde (u ,v);
    }
    
    vector <int> vec;
    for (int i = 1 ;i <= n ;i ++)
        vec.push_back (i);
    
    flag = 0;
    brkdwn (vec);
    
    if (flag == 0)
        cout << "TAK" << endl;
    else
        cout << "NIE" << endl;

    return ;
}


signed main()
{
	I AK CSP

    int T;
    cin >> T;

    while (T --)
        Gogogo ();
        
	return !!!!! ("ShZhao" && "SHzhao");
}
//Code by Lyyq.
//wage.

::::

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;
}