Good Graph

7000ms

262144K

Description:

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:

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:

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.

Sample Input:

Sample Output:

Sample Input:

Sample Output:

NO
2
2 3

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.

Informação

Provedor Codeforces

Código CF1835F