406426: GYM102399 J Конкурс котиков

J. Конкурс котиковограничение по времени на тест2 секундыограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

В Котовице в ближайшие выходные будет проходить конкурс котиков. Для конкурса нужно выбрать жюри и участников. Всего в Котовице $$$n$$$ жителей, и у каждого жителя живет ровно один котик. Жители и котики пронумерованы целыми числами от $$$1$$$ до $$$n$$$, причем у $$$i$$$-го жителя живёт $$$i$$$-й котик.

Каждый житель Котовице знаком с несколькими котиками, включая, конечно же, своего. Для конкурса нужно выбрать нескольких жителей на роль жюри, и нескольких котиков на роль участников. Для того чтобы конкурс состоялся, в нём должен принять участие хотя бы один член жюри, и хотя бы один участник. Для того чтобы конкурс прошёл честно, ни один член жюри не должен быть знаком ни с одним участником. И, наконец, чтобы конкурс прошёл наиболее интересно, было решено, что количество членов жюри плюс количество участников должно равняться $$$n$$$.

Помогите жителям Котовице выбрать состав жюри и участников для предстоящего конкурса, либо определите, что это сделать невозможно.

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 100\,000$$$) — количество тестовых случаев. Затем следует описание $$$t$$$ тестовых случаев, каждый из которых задан следующим образом:

В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le m \le 10^6$$$) — количество жителей в Котовице и количество пар знакомых жителей и котиков, соответственно.

В следующих $$$m$$$ строках заданы пары целых чисел $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$), обозначающих, что $$$a_i$$$-й житель знаком с $$$b_i$$$-м котиком. Каждая пара жителя и котика встречается в списке знакомых не более одного раза. Гарантируется, что для любого $$$i$$$ в списке присутствует пара из $$$i$$$-го жителя и $$$i$$$-го котика.

Тестовые случаи разделены одной пустой строкой.

Гарантируется, что сумма $$$n$$$ по всем тестам не превосходит $$$10^6$$$, и сумма $$$m$$$ по всем тестам не превосходит $$$10^6$$$.

Выходные данные

Для каждого теста в единственной строке выведите «No», если выбрать состав жюри и участников для конкурса невозможно. Иначе, в первой строке выведите «Yes». Во второй строке выведите два целых числа $$$j$$$ и $$$p$$$ ($$$1 \le j$$$, $$$1 \le p$$$, $$$j + p = n$$$) — количество членов жюри и участников в конкурсе, соответственно. В третьей строке выведите $$$j$$$ различных целых чисел от $$$1$$$ до $$$n$$$ — номера жителей, которые должны быть выбраны на роль жюри. В четвертой строке выведите $$$p$$$ различных целых чисел от $$$1$$$ до $$$n$$$ — номера котиков, которые должны быть выбраны на роль участников. Если различных подходящих ответов несколько, можно вывести любой из них.

ПримерВходные данные

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

Выходные данные

Yes
2 1
1 3 
2 
Yes
1 2
2 
1 3 
No
No

Примечание

В первом тесте на роль жюри можно выбрать первого и третьего жителя, ни один из них не знаком со вторым котиком, поэтому его можно выбрать на роль участника.

Во втором тесте на роль жюри можно выбрать второго жителя, он не знаком ни с первым, ни с третьим котиком, которых можно выбрать на роль участников.

В третьем тесте ответа не существует, потому что единственный житель знаком с единственным котиком. Поэтому они не могут участвовать в конкурсе одновременно. Значит, в конкурсе не будет участвовать ни один житель, либо ни один котик.

В четвертом тесте, аналогично третьему, каждый житель знаком с каждым котиком, поэтому в конкурсе не могут одновременно участие какой-то житель и какой-то котик.