D. Catowice City

In the Catowice city next weekend the cat contest will be held. However, the jury members and the contestants haven't been selected yet. There are ?? residents and ?? cats in the Catowice, and each resident has exactly one cat living in his house. The residents and cats are numbered with integers from 1 to ??, where the ??-th cat is living in the house of ??-th resident.

Each Catowice resident is in friendship with several cats, including the one living in his house. In order to conduct a contest, at least one jury member is needed and at least one cat contestant is needed. Of course, every jury member should know none of the contestants. For the contest to be successful, it's also needed that the number of jury members plus the number of contestants is equal to ??.

Please help Catowice residents to select the jury and the contestants for the upcoming competition, or determine that it's impossible to do.

Input

The first line contains an integer ?? (1≤??≤100000), the number of test cases. Then description of ?? test cases follow, where each description is as follows:

The first line contains integers ?? and ?? (1≤??≤??≤106), the number of Catowice residents and the number of friendship pairs between residents and cats.

Each of the next ?? lines contains integers ???? and ???? (1≤????,????≤??), denoting that ????-th resident is acquaintances with ????-th cat. It's guaranteed that each pair of some resident and some cat is listed at most once.

It's guaranteed, that for every ?? there exists a pair between ??-th resident and ??-th cat.

Different test cases are separated with an empty line.

It's guaranteed, that the sum of ?? over all test cases is at most 106 and that the sum of ?? over all test cases is at most 106.

Output

For every test case print:

"No", if it's impossible to select the jury and contestants.
Otherwise print "Yes".
In the second line print two integers ?? and ?? (1≤??, 1≤??, ??+??=??) — the number of jury members and the number of contest participants.

In the third line print ?? distinct integers from 1 to ??, the indices of the residents forming a jury.

In the fourth line print ?? distinct integers from 1 to ??, the indices of the cats, which will participate in the contest.

In case there are several correct answers, print any of them.

Example

input
4
3 4
1 1
2 2
3 3
1 3

3 7
1 1
1 2
1 3
2 2
3 1
3 2
3 3

1 1
1 1

2 4
1 1
1 2
2 1
2 2
output
Yes
2 1
1 3
2
Yes
1 2
2
1 3
No
No

Note

In the first test case, we can select the first and the third resident as a jury. Both of them are not acquaintances with a second cat, so we can select it as a contestant.

In the second test case, we can select the second resident as a jury. He is not an acquaintances with a first and a third cat, so they can be selected as contestants.

In the third test case, the only resident is acquaintances with the only cat, so they can't be in the contest together. So it's not possible to make a contest with at least one jury and at least one cat.

In the fourth test case, each resident is acquaintances with every cat, so it's again not possible to make a contest with at least one jury and at least one cat.

題意

有n個人，有n只貓；有m個關系，每個關系用(x,y)表示，表示為第x個人認識第y只貓。現在小鎮要舉行比賽，現在讓你選出貓和人參加比賽，一共要選擇n個出來，但需要保證至少一個人和一只貓，且人和貓都不認識。這道題保證第i個人認識第i只貓。

題解

我們依次了解以下的知識點：

1. 因為第i個人知道第j只貓，所以選了第i個人就不會選第i只貓；選了第i只貓就不會選第i個人。由于要選n個，所以要么選了第i個人，要么就必須選擇第i只貓。

2. 如果選了第i個人，第i個人認識第j只貓，所以第j只貓不能選，所以第j個人就必須選。翻譯一下，我們以(i,j)建邊，表示選了i就必須選擇j，然后如果存在聯通塊，就表示這個聯通塊的東西都必須選。

所以這道題就是判斷否存在一個大小小于n的聯通塊存在即可。枚舉第一個人選擇貓，還是選擇人即可。

代碼

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+7;
int t,n,m;
vector<int> E[2][maxn];
int vis[2][maxn],cnt=0;
void dfs1(int x,int z){
	vis[z][x]=1;
	cnt++;
	for(int i=0;i<E[z][x].size();i++){
		int v=E[z][x][i];
		if(vis[z][v])continue;
		dfs1(v,z);
	}
}
void clear(){
	for(int i=1;i<=n;i++){
		vis[0][i]=vis[1][i]=0;
		E[0][i].clear();
		E[1][i].clear();
	}
}
void solve(){
	scanf("%d%d",&n,&m);
	clear();
	for(int i=0;i<m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		E[0][x].push_back(y);
		E[1][y].push_back(x);
	}

	for(int z=0;z<2;z++){
		cnt=0;
		dfs1(1,z);
		if(cnt<n){
			puts("Yes");
			if(z==0){
				cout<<cnt<<" "<<n-cnt<<endl;
			} else {
				cout<<n-cnt<<" "<<cnt<<endl;
			}
			for(int i=1;i<=n;i++){
				if(vis[z][i]==1-z)cout<<i<<" ";
			}
			cout<<endl;
			for(int i=1;i<=n;i++){
				if(vis[z][i]==z)cout<<i<<" ";
			}
			cout<<endl;
			return;
		}
	}
	puts("No");
}
int main(){
	scanf("%d",&t);
	while(t--)solve();
	return 0;
}