J. Japanese Samurai Fight
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Banshū is an old province in Japan that is known for being home of some of the best samurais of all time. Currently, $$$N$$$ samurais live there and are preparing themselves for their annual celebration where some of the best samurais fight against each other. As you may know, samurais rely on respect as the base for their communities. This respect is mutual, meaning that if samurai $$$a$$$ respects samurai $$$b$$$, then samurai $$$b$$$ respects samurai $$$a$$$, too. One caveat is that this relation is not transitive.

For the main event of the celebration, they want to pick two of the highest respected samurais. Since they don't want to pick specific participants yet, they want to divide all samurais into two non-empty subsets, $$$S_1$$$ and $$$S_2$$$, such that all members, $$$s_1$$$ and $$$s_2$$$ respectively, of each subset are good candidates for the main fight. A good candidate for the fight is a samurai $$$s$$$ who is respected by all the members of the subset $$$S$$$ to which it belongs. No samurai should be left out of this selection process ($$$|S_1| + |S_2| = N$$$).

They're currently unsure if this is possible, so they've come to you for help. Given that there's still some time until the celebration, you've taken the task to try and make it happen. For this, you know that if you introduce two samurais while giving them their favorite sake, it's certain that they will end up respecting each other.

Having this strategy in mind, you want to know if by introducing some samurais to respect each other, you're capable of dividing the whole population in subsets $$$S_1$$$ and $$$S_2$$$ such that the fight can take place.

But you've got to hurry! Theres not much time left and you've to pick your introductions wisely as they're not unlimited.

Input

For the first line of the input you get two integers $$$N$$$ ($$$1 \leq N \leq 1000)$$$ and $$$M$$$ ($$$0 \leq M \leq \frac{N(N-1)}{2}$$$), that represent the number of samurais in the province and the number of already known relationships between them, respectively.

For each of the next $$$M$$$ lines you get two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a_i \neq b_i \leq N$$$), that represent the indices of the two samurais that already respect to each other.

Output

For the first line of the output print "YES" (without quotes) if it is possible to make the fight happen, and "NO" otherwise.

If the answer is "YES", then in the next line print $$$K$$$ $$$(0 \leq K \leq \frac{N (N-1)}{4})$$$ - the number of introductions that will take place to make it happen.

For each of the next $$$K$$$ lines, print two integers: $$$u$$$ and $$$v$$$ $$$(1 \leq u_i \neq v_i \leq N)$$$, the indices of the samurais that will end up respecting each other during the $$$i$$$-th introduction. You can't print duplicated introductions.

Examples
Input
1 0
Output
NO
Input
2 1
1 2
Output
YES
0
Input
6 4
1 2
1 3
2 3
4 5
Output
YES
2
4 6
5 6