The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

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.

dfs and similar

dsu

graphs

*2300

No tag edit access

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

×
E. Interesting Graph and Apples

time limit per test

1 secondmemory limit per test

64 megabytesinput

standard inputoutput

standard outputHexadecimal likes drawing. She has drawn many graphs already, both directed and not. Recently she has started to work on a still-life «interesting graph and apples». An undirected graph is called interesting, if each of its vertices belongs to one cycle only — a funny ring — and does not belong to any other cycles. A funny ring is a cycle that goes through all the vertices just once. Moreover, loops are funny rings too.

She has already drawn the apples and some of the graph edges. But now it is not clear, how to connect the rest of the vertices to get an interesting graph as a result. The answer should contain the minimal amount of added edges. And furthermore, the answer should be the lexicographically smallest one. The set of edges (*x*_{1}, *y*_{1}), (*x*_{2}, *y*_{2}), ..., (*x*_{n}, *y*_{n}), where *x*_{i} ≤ *y*_{i}, is lexicographically smaller than the set (*u*_{1}, *v*_{1}), (*u*_{2}, *v*_{2}), ..., (*u*_{n}, *v*_{n}), where *u*_{i} ≤ *v*_{i}, provided that the sequence of integers *x*_{1}, *y*_{1}, *x*_{2}, *y*_{2}, ..., *x*_{n}, *y*_{n} is lexicographically smaller than the sequence *u*_{1}, *v*_{1}, *u*_{2}, *v*_{2}, ..., *u*_{n}, *v*_{n}. If you do not cope, Hexadecimal will eat you. ...eat you alive.

Input

The first line of the input data contains a pair of integers *n* and *m* (1 ≤ *n* ≤ 50, 0 ≤ *m* ≤ 2500) — the amount of vertices and edges respectively. The following lines contain pairs of numbers *x*_{i} and *y*_{i} (1 ≤ *x*_{i}, *y*_{i} ≤ *n*) — the vertices that are already connected by edges. The initial graph may contain multiple edges and loops.

Output

In the first line output «YES» or «NO»: if it is possible or not to construct an interesting graph. If the answer is «YES», in the second line output *k* — the amount of edges that should be added to the initial graph. Finally, output *k* lines: pairs of vertices *x*_{j} and *y*_{j}, between which edges should be drawn. The result may contain multiple edges and loops. *k* can be equal to zero.

Examples

Input

3 2

1 2

2 3

Output

YES

1

1 3

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/28/2023 07:11:02 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|