Codeforces Round 880 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

bitmasks

dfs and similar

graph matchings

graphs

implementation

*3500

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Good Graph

time limit per test

7 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

Examples

Input

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/06/2024 02:06:50 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|