A16057 | Good Graph

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.

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$ .

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.