Good Graph
Contest: Codeforces Round 880 (Div. 1)
Difficulty rating: 3500
Tags: bitmasks, dfs and similar, graph matchings, graphs, implementation

You are given a bipartite graph $$$G$$$ with the vertex set in the left part $$$L$$$, in the right part $$$R$$$, and $$$m$$$ edges connecting these two sets. We know that $$$|L| = |R| = n$$$.

For any subset $$$S \subseteq L$$$, let $$$N(S)$$$ denote the set of all neighbors of vertices in $$$S$$$. We say that a subset $$$S \subseteq L$$$ in graph $$$G$$$ is tight if $$$|S| = |N(S)|$$$. We say that graph $$$G$$$ is good if $$$\forall_{S \subseteq L}, |S| \leq |N(S)|$$$.

Your task is to verify whether the graph is good and, if so, to optimize it. If the graph is not good, find a subset $$$S \subseteq L$$$ such that $$$|S| > |N(S)|$$$. However, if the graph is good, your task is to find a good bipartite graph $$$G'$$$ with the same set of vertices $$$L \cup R$$$, in which $$$\forall_{S \subseteq L}$$$, $$$S$$$ is tight in $$$G$$$ if and only if $$$S$$$ is tight in $$$G'$$$. If there are multiple such graphs, choose one with the smallest possible number of edges. If there are still multiple such graphs, print any.

Input format:
The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^3$$$, $$$0 \leq m \leq n^2$$$), separated by a single space. The number $$$n$$$ denotes the number of vertices in each of the sets $$$L$$$ and $$$R$$$, and the number $$$m$$$ denotes the number of edges between them.

The following $$$m$$$ lines describe the edges. Each of them contains two integers $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq n$$$, $$$n+1 \leq r \leq 2 \cdot n$$$), separated by a single space, indicating that there is an edge from vertex $$$l \in L$$$ to vertex $$$r \in R$$$.

Output format:
If the graph $$$G$$$ given in the input is not good, output one word "NO" in the first line of the output. In the second line of the output, output the number $$$k$$$, and in the third line, output $$$k$$$ numbers $$$l_1, l_2, \dots, l_k$$$, separated by single spaces. These numbers should indicate that for the set $$$S = \{l_1, l_2, \dots, l_k\}$$$, $$$|S| > |N(S)|$$$.

However, if the graph $$$G$$$ given in the input is good, output one word "YES" in the first line of the output. In the second line of the output, output the number $$$m'$$$, indicating the number of edges in the new, also good graph $$$G'$$$. Then, in the following $$$m'$$$ lines, output the edges of the graph $$$G'$$$ in the same format as given in the input.

Constraints:
Time limit: 7.0 s
Memory limit: 256.0 MB

Note:
In the first sample test, the graph $$$G$$$ is good; thus, we are looking for an equivalent graph with the same tight sets. The only tight set is $$$\{ 1, 2, 3 \}$$$, which remains tight in the resulting graph. Moreover, no other set is tight in the resulting graph. One can prove that no graph with less than $$$6$$$ edges and the same tight sets exists.

In the second sample test, the graph $$$G$$$ is not good. Set $$$\{ 2, 3 \}$$$ has only one neighbour — vertex $$$6$$$. Thus, $$$|\{ 2, 3 \}| > |\{ 6 \}|$$$, which is a prove that the input graph is not good.

Example input:
3 8
1 4
1 5
1 6
2 4
2 5
2 6
3 5
3 6

Example output:
YES
6
1 4
1 5
2 5
2 6
3 6
3 4

Example input:
3 4
1 4
1 5
2 6
3 6

Example output:
NO
2
2 3

Editorial:
According to Hall's theorem, a graph is good if and only if a perfect matching exists. We run any reasonable algorithm to find a perfect matching (e.g. the Hopcroft-Karp's algorithm). We call the found matching $$$\mathcal{M}$$$ (any perfect matching is fine).
We look for a counterexample if we do not find a perfect matching. One way to find it is to run s similar DFS as in the Hopcroft-Karp algorithm from any unmatched vertex on the left side. As a reminder, we visit all neighbours of vertices on the left side and only the vertex with which we are matched for vertices on the right side. As we won't see any unmatched vertex on the right side (otherwise, we'd found an augmenting path), the set of visited vertices on the left side has fewer neighbours than its size — we found our counterexample.
As our graph is good, we should examine the construction of tight sets.
Lemma 1
Function $$$N(S)$$$ is submodular.
Proof
Consider two sets $$$A \subseteq B$$$ and a vertex $$$v \notin B$$$. For each vertex $$$u \in N(B + v) \setminus N(B)$$$, we know that $$$u \in N(A + v)$$$ and $$$u \notin N(A)$$$, thus, $$$u \in N(A + v) \setminus N(A)$$$. We conclude that $$$|N(B + v) \setminus N(B)| \leq |N(A + v) \setminus N(A)|$$$; thus, the function is submodular.
Lemma 2
Tight sets are closed under intersection and sum.
Proof
Consider two tight sets, $$$A$$$ and $$$B$$$. From Lemma 1, we get that $$$|A| + |B| = |N(A)| + |N(B)| \geq |N(A \cup B)| + |N(A \cap B)| \geq |A \cup B| + |A \cap B| = |A| + |B|$$$, where the last inequality results from the graph being good. As we get the same value on both sides, all inequalities become equalities. In particular, with the graph being good, we get that $$$|N(A \cup B)| = |A \cup B|$$$ and $$$|N(A \cap B)| = |A \cap B|$$$. That proves that sets $$$A \cup B$$$, and $$$A \cap B$$$ are tight.
We define $$$T(v)$$$ as the minimal tight set containing vertex $$$v$$$. We know such a set exists as tight sets are closed under the intersection. From that, we can conclude that any tight set can be represented as a sum of minimal tight sets. Thus, we are only interested in keeping the same minimal tight sets. We can find the minimal tight sets using the same DFS algorithm as for finding a counterexample. As the graph is large, use bitsets to optimise it.
To find the smallest graph, we analyse these sets in order of nondecreasing sizes. For simplicity, we erase duplicates. When we analyse the set, we distinguish the new vertices (the ones that haven't been touched yet). There is always a new vertex, as this is the minimal tight set for at least one vertex (and we removed duplicates). If there is only one new vertex $$$v$$$, we can add an edge from $$$v$$$ to $$$M(v)$$$. Otherwise, we have to connect these vertices $$$v_1, v_2, \ldots, v_k$$$ into a cycle — we create edges $$$\langle v_1, M(v_1) \rangle, \langle M(v_1), v_2, \rangle \ldots, \langle v_k, M(v_k) \rangle, \langle M(v_k), v_1 \rangle$$$. If we have less than $$$2 \cdot k$$$ edges, then there exists a vertex $$$v_i$$$ with a degree equal to $$$1$$$ — we could pick this vertex, and it'd create a minimal tight set.
We still have to handle other vertices in this (i.e. the ones which are not new). We pick a representative $$$v$$$ for our cycle, which will become a representative for this set. Similarly, we have a representative for other sets. We find a partition of these vertices into a minimal number of tight sets. We add an edge between these representatives and our vertex $$$v$$$. We use a similar argument as before — if we didn't add this edge, we would find different minimal tight sets. To handle representatives, we use a disjoint set union structure.
The final complexity of this algorithm is $$$\mathcal{O}(N^3 / 64)$$$.