F. Хороший граф
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан двудольный граф $$$G$$$ с множеством вершин в левой доле $$$L$$$, в правой доле $$$R$$$ и $$$m$$$ ребрами, соединяющими эти два множества. Мы знаем, что $$$|L| = |R| = n$$$.

Для любого подмножества $$$S \subseteq L$$$, пусть $$$N(S)$$$ обозначает множество всех соседей вершин в $$$S$$$. Мы говорим, что подмножество $$$S \subseteq L$$$ в графе $$$G$$$ является строгим, если $$$|S| = |N(S)|$$$. Мы говорим, что граф $$$G$$$ является хорошим, если $$$\forall_{S \subseteq L}, |S| \leq |N(S)|$$$.

Ваша задача — проверить, является ли граф хорошим, и, если да, то оптимизировать его. Если граф не является хорошим, найдите подмножество $$$S \subseteq L$$$ такое, что $$$|S| > |N(S)|$$$. Однако, если граф хороший, ваша задача — найти хороший двудольный граф $$$G'$$$ с тем же набором вершин $$$L \cup R$$$, в котором $$$\forall_{S \subseteq L}$$$ множество $$$S$$$ является строгим в $$$G$$$ тогда и только тогда, когда $$$S$$$ строго в $$$G'$$$. Если таких графов несколько, выберите один с наименьшим возможным числом ребер. Если таких графов по-прежнему несколько, выведите любой из них.

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

Первая строка входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n \leq 10^3$$$, $$$0 \leq m \leq n^2$$$), разделенных пробелом. Число $$$n$$$ обозначает количество вершин в каждом из множеств $$$L$$$ и $$$R$$$, а число $$$m$$$ — количество ребер между ними.

Следующие $$$m$$$ строк описывают ребра. Каждая из них содержит два целых числа $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq n$$$, $$$n+1 \leq r \leq 2 \cdot n$$$), разделенных пробелом, что указывает на наличие ребра из вершины $$$l \in L$$$ в вершину $$$r \in R$$$.

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

Если граф $$$G$$$, заданный на входе, не является хорошим, выведите в первой строке вывода одно слово «NO». Во второй строке вывода выведите число $$$k$$$, а в третьей строке выведите $$$k$$$ чисел $$$l_1, l_2, \dots, l_k$$$, разделенные пробелами. Эти числа должны показать, что для множества $$$S = \{l_1, l_2, \dots, l_k\}$$$ выполняется $$$|S| > |N(S)|$$$.

Однако, если граф $$$G$$$, заданный на входе, хороший, выведите одно слово «YES» в первой строке вывода. Во второй строке вывода выведите число $$$m'$$$, обозначающее количество ребер в новом, также хорошем графе $$$G'$$$. Затем, в следующих $$$m'$$$ строках, выведите ребра графа $$$G'$$$ в том же формате, что и во входных данных.

Примеры
Входные данные
3 8
1 4
1 5
1 6
2 4
2 5
2 6
3 5
3 6
Выходные данные
YES
6
1 4
1 5
2 5
2 6
3 6
3 4
Входные данные
3 4
1 4
1 5
2 6
3 6
Выходные данные
NO
2
2 3
Примечание

В первом тестовом примере граф $$$G$$$ хороший; таким образом, мы ищем эквивалентный граф с такими же строгими множествами. Единственный строгий набор — это $$$\{ 1, 2, 3 \}$$$, который остается строгим в результирующем графе. Более того, никакое другое множество не является строгим в полученном графе. Можно доказать, что не существует графа с менее чем $$$6$$$ ребрами и такими же строгимимножествами.

Во втором тестовом примере граф $$$G$$$ не является хорошим. Множество $$$\{ 2, 3 \}$$$ имеет только одного соседа — вершину $$$6$$$. Таким образом, $$$|\{ 2, 3 \}| > |\{ 6 \}|$$$, что доказывает, что входной граф не является хорошим.