D. Catowice City--（2-sat)

D. Catowice City--（2-sat)

2-sat简介

也就是有0/1两种状态，最后必须要每个人有一种状态，并且选够n个。
一般是设立两个点x,x+n然后判断是否有矛盾。

不同

这题建图后会发现x和x+n这两个图是没有交集的，所以只需要建立一个图。
至于是人还是猫，只需要确定最后一个，就可以了，也就是color最小的这个点，他一定是没有度数的，并且不会对其他人产生影响。

代码

/*
出了自己到自己不建立边之外
其他的都需要建立边 

1-n表示人 n+1-2n表示猫 

1
1 1
1 1

需要保证至少有一个人是0 

因为根据列出的关系
发现是x->y建边
x+n->y+n建边 ，两者其实是不会有交集的，只需要建立一次边就可以了
然后进行跑图，选择第一个连通分量为人，或者是什么，因为不会对后面产生影响 
*/

#include <bits/stdc++.h>
using namespace std;
#define int long long
using pii=pair<int,int>;
#define hr cout<<"-------------------------------------\n"
#define br cout<<'\n';
#define fi first
#define se second
const int M=1e6+5;

int n,m;

int h[M],ne[M<<1],e[M<<1],tot;
void add(int a,int b) {
	e[++tot]=b; ne[tot]=h[a]; h[a]=tot;
}

int dfn[M],low[M],cnt;
int color[M],siz[M],scnt;
stack<int>st;
int vis[M];
void tarjan(int now) {
	dfn[now]=low[now]=++cnt;
	st.push(now);
	vis[now]=1;
	for(int i=h[now];i;i=ne[i]) {
		int to=e[i];
		if(dfn[to]==0) {
			tarjan(to);
			low[now]=min(low[now],low[to]);
		}
		else if(vis[to])low[now]=min(low[now],dfn[to]);
	}
	if(dfn[now]==low[now]) {
		scnt++;
		while(1) {
			int k=st.top();st.pop();vis[k]=0;
			color[k]=scnt;
			siz[scnt]++;
			if(k==now)break;
		}
	}
}

void print() {
	if(scnt==1) {
		cout<<"No\n";
		return ;
	}
	cout<<"Yes\n";
	cout<<siz[1]<<' '<<n-siz[1]<<'\n';
	for(int i=1;i<=n;i++)if(color[i]==1)cout<<i<<' ';cout<<'\n';
	for(int i=1;i<=n;i++)if(color[i]!=1)cout<<i<<' ';cout<<'\n'; 
	//必须要保证至少有一个人，或者一只猫才可以 
	
}

void init() {
	tot=scnt=cnt=0;
	for(int i=1;i<=n;i++) {
		dfn[i]=low[i]=h[i]=0;
		color[i]=vis[i]=siz[i]=0;
	}
}

int another(int x) {
	return x+n;
}

void solve() {
	cin>>n>>m;
	init(); 
	for(int i=1;i<=m;i++) {
		int x,y;
		cin>>x>>y;
		if(x==y)continue; 
		add(x,y);//两者都选人 
//		add(another(y),another(x));//或者两者都选猫 ，那么没必要加倍了 
	}
	for(int i=1;i<=n;i++)if(dfn[i]==0)tarjan(i);
	print();
}

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int TT;cin>>TT;while(TT--)
	solve();
	return 0;
}