Вам дан двудольный граф \(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'\). Если таких графов несколько, выберите один с наименьшим возможным числом ребер. Если таких графов по-прежнему несколько, выведите любой из них.
Выходные данные
Если граф \(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'\) в том же формате, что и во входных данных.
Примечание
В первом тестовом примере граф \(G\) хороший; таким образом, мы ищем эквивалентный граф с такими же строгими множествами. Единственный строгий набор — это \(\{ 1, 2, 3 \}\), который остается строгим в результирующем графе. Более того, никакое другое множество не является строгим в полученном графе. Можно доказать, что не существует графа с менее чем \(6\) ребрами и такими же строгимимножествами.
Во втором тестовом примере граф \(G\) не является хорошим. Множество \(\{ 2, 3 \}\) имеет только одного соседа — вершину \(6\). Таким образом, \(|\{ 2, 3 \}| > |\{ 6 \}|\), что доказывает, что входной граф не является хорошим.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
3 4
1 4
1 5
2 6
3 6
|
NO
2
2 3
|