310452: CF1835F. Good Graph

F. Good Graphtime limit per test7 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

ExamplesInput

3 8
1 4
1 5
1 6
2 4
2 5
2 6
3 5
3 6

Output

YES
6
1 4
1 5
2 5
2 6
3 6
3 4

Input

3 4
1 4
1 5
2 6
3 6

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.

题目大意：
给定一个二部图\( G \)，其顶点集分为左部\( L \)和右部\( R \)，且两部分顶点数相等，即\( |L| = |R| = n \)。图中包含\( m \)条边连接这两部分。对于任何子集\( S \subseteq L \)，定义\( N(S) \)为集合\( S \)中所有顶点的邻接顶点集合。如果对于某个子集\( S \subseteq L \)，有\( |S| = |N(S)| \)，则称\( S \)在图\( G \)中是“紧的”。如果对于所有\( S \subseteq L \)，都有\( |S| \leq |N(S)| \)，则称图\( G \)是“好的”。

任务是判断给定的图是否是好的，如果它是好的，则优化它；如果它不是好的，则找出一个子集\( S \subseteq L \)，使得\( |S| > |N(S)| \)。如果图是好的，则需要找到一个具有相同顶点集\( L \cup R \)的好二部图\( G' \)，使得\( S \)在\( G \)中是紧的当且仅当在\( G' \)中也是紧的。如果有多个这样的图，选择边数最少的；如果仍有多个，则输出其中任意一个。

输入输出数据格式：
输入：
- 第一行包含两个整数\( n \)和\( m \)（\( 1 \leq n \leq 10^3 \)，\( 0 \leq m \leq n^2 \)），分别表示左右两部分顶点的数量和边的数量。
- 接下来的\( m \)行，每行包含两个整数\( l \)和\( r \)（\( 1 \leq l \leq n \)，\( n+1 \leq r \leq 2 \cdot n \)），表示从左部顶点\( l \)到右部顶点\( r \)的一条边。

输出：
- 如果图\( G \)不是好的，则在第一行输出“NO”，在第二行输出集合\( S \)中元素的数量\( k \)，在第三行输出集合\( S \)中的\( k \)个元素，以空格分隔。
- 如果图\( G \)是好的，则在第一行输出“YES”，在第二行输出新图\( G' \)中边的数量\( m' \)，然后在接下来的\( m' \)行中按输入格式输出\( G' \)的边。题目大意： 给定一个二部图\( G \)，其顶点集分为左部\( L \)和右部\( R \)，且两部分顶点数相等，即\( |L| = |R| = n \)。图中包含\( m \)条边连接这两部分。对于任何子集\( S \subseteq L \)，定义\( N(S) \)为集合\( S \)中所有顶点的邻接顶点集合。如果对于某个子集\( S \subseteq L \)，有\( |S| = |N(S)| \)，则称\( S \)在图\( G \)中是“紧的”。如果对于所有\( S \subseteq L \)，都有\( |S| \leq |N(S)| \)，则称图\( G \)是“好的”。 任务是判断给定的图是否是好的，如果它是好的，则优化它；如果它不是好的，则找出一个子集\( S \subseteq L \)，使得\( |S| > |N(S)| \)。如果图是好的，则需要找到一个具有相同顶点集\( L \cup R \)的好二部图\( G' \)，使得\( S \)在\( G \)中是紧的当且仅当在\( G' \)中也是紧的。如果有多个这样的图，选择边数最少的；如果仍有多个，则输出其中任意一个。 输入输出数据格式： 输入： - 第一行包含两个整数\( n \)和\( m \)（\( 1 \leq n \leq 10^3 \)，\( 0 \leq m \leq n^2 \)），分别表示左右两部分顶点的数量和边的数量。 - 接下来的\( m \)行，每行包含两个整数\( l \)和\( r \)（\( 1 \leq l \leq n \)，\( n+1 \leq r \leq 2 \cdot n \)），表示从左部顶点\( l \)到右部顶点\( r \)的一条边。 输出： - 如果图\( G \)不是好的，则在第一行输出“NO”，在第二行输出集合\( S \)中元素的数量\( k \)，在第三行输出集合\( S \)中的\( k \)个元素，以空格分隔。 - 如果图\( G \)是好的，则在第一行输出“YES”，在第二行输出新图\( G' \)中边的数量\( m' \)，然后在接下来的\( m' \)行中按输入格式输出\( G' \)的边。