Catowice City
Contest: Codeforces Round 594 (Div. 1)
Difficulty rating: 2400
Tags: 2-sat, dfs and similar, graph matchings, graphs

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 $$$n$$$ residents and $$$n$$$ 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 $$$n$$$, where the $$$i$$$-th cat is living in the house of $$$i$$$-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 $$$n$$$.

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

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 100\,000$$$), the number of test cases. Then description of $$$t$$$ test cases follow, where each description is as follows:

The first line contains integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le m \le 10^6$$$), the number of Catowice residents and the number of friendship pairs between residents and cats.

Each of the next $$$m$$$ lines contains integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$), denoting that $$$a_i$$$-th resident is acquaintances with $$$b_i$$$-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 $$$i$$$ there exists a pair between $$$i$$$-th resident and $$$i$$$-th cat.

Different test cases are separated with an empty line.

It's guaranteed, that the sum of $$$n$$$ over all test cases is at most $$$10^6$$$ and that the sum of $$$m$$$ over all test cases is at most $$$10^6$$$.

Output format:
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 $$$j$$$ and $$$p$$$ ($$$1 \le j$$$, $$$1 \le p$$$, $$$j + p = n$$$) — the number of jury members and the number of contest participants.In the third line print $$$j$$$ distinct integers from $$$1$$$ to $$$n$$$, the indices of the residents forming a jury.In the fourth line print $$$p$$$ distinct integers from $$$1$$$ to $$$n$$$, the indices of the cats, which will participate in the contest.In case there are several correct answers, print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

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.

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

Example output:
Yes
2 1
1 3 
2 
Yes
1 2
2 
1 3 
No
No

Editorial:
You are given bipartite graph and a perfect matching in it. You have to find independent set of size $$$n$$$ which doesn't coincide with either of two parts.
Suppose such independent set exists, let's call it $$$S$$$. Also, let's call left part of graph as $$$L$$$ and right part of graph as $$$R$$$. Then define $$$A = S \cap L$$$, $$$B = L \setminus A$$$, $$$A'$$$ is set of all nodes which are connected by edges from matching with $$$A$$$, $$$B'$$$ — similarly for $$$B$$$. It's easy to see that $$$S = A \cup B'$$$.
Let's direct all edges in graph. Edges from matching will be directed from right to left, and all other edges will be directed from left to right. Now edges from matching will direct from $$$A'$$$ to $$$A$$$ and from $$$B'$$$ to $$$B$$$. Other edges could direct from $$$A$$$ to $$$A'$$$, from $$$B$$$ to $$$B'$$$ and from $$$B$$$ to $$$A'$$$. Observe that edges cannot direct from $$$A$$$ to $$$B'$$$, cause it wouldn't be an independent set otherwise.
It's easy to see that $$$B'$$$ isn't reachable from $$$A$$$. So, let's find all strongly connected components (SCC) in this graph. If there's only one such component, answer doesn't exist due to the fact that any node of $$$B'$$$ isn't reachable from any node of $$$A$$$. If SCC is only one, any node is reachable from any other node therefore in this case either $$$A$$$ or $$$B'$$$ are empty. If there are at least two SCC, let's choose any source SCC and call it $$$Q$$$. Consider $$$B' = Q \cap R$$$ and define $$$A$$$ as set of all nodes in left part which are not connected by edges from matching with $$$B'$$$. Let's proof that if some $$$l \in L$$$ lies in $$$B'$$$, then $$$r$$$ — pair of $$$l$$$ in matching also lies in $$$B'$$$. That's obvious since there are no incoming edges in $$$B'$$$ and there's edge from $$$r$$$ to $$$l$$$. So, none of nodes from $$$A$$$ will lay in chosen SCC. Thus $$$B'$$$ won't be reachable from $$$A$$$ and $$$A \cup B'$$$ will be an independent set.
The only exception is $$$n = 1$$$, in such case there are two SCC but answer doesn't exist (cause chosen $$$A$$$ will be empty).