405901: GYM102155 C Block, Stock and Two Smoking Galaxy Notes

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Block, Stock and Two Smoking Galaxy Notestime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

I decided to start a new fancy project related to cryptocurrency, deep learning, self-driving cars and maybe mobile voice assistance (will decide that later). I already have a team consisting of n promising software engineers and last thing that has to be done is choosing a techlead among them.

All engineers except the techlead should be divided into teams consisting of one or two engineers (recently I read first ten pages of the book "Agile Software Development: Programming in Pairs" and found the described technique very useful!). For each pair of engineers I know if they can interact with each other effectively.

The choice of techlead and distribution into teams is effective if any two-member team consists of two engineers that can interact effectively, and in any team there is at least one engineer who can interact effectively with the techlead.

I want you to find an appropriate company structure as fast as possible, so that our startup can make an IPO or ICO (not quite sure yet what that means, no time for that now), or determine that it is impossible and the world of success and glory is not for me (at least for today).

Input

The first line of input contains two integers n and m (2 ≤ n ≤ 1000, 0 ≤ m ≤ 10 000), the number of software engineers and the number of successfully interacting pairs.

Each of the next m lines contains two integers ui, vi (1 ≤ ui, vi ≤ n, ui ≠ vi), the indices of engineers forming an effectively interacting pair.

I guarantee that all unordered pairs of engineers are different.

Output

Print a single word "No" if it is impossible to create a company structure satisfying my requirements.

Otherwise, print a word "Yes" in the first line.

In the second line print two integers l, k (1 ≤ l ≤ n, ), the index of the techlead and the number of teams.

Each of the next k lines should contain two integers t1 and t2 defining a team. If the team consists of two members, t1 and t2 should be indices of the engineers forming it, otherwise t1 should be the index of the only engineer in the team and t2 should be  - 1.

If there are multiple correct answers, print any of them.

ExamplesInput
5 4
1 2
2 3
3 4
4 5
Output
Yes
3 2
2 1
4 5
Input
4 4
1 2
2 3
3 4
4 1
Output
Yes
1 2
2 3
4 -1
Input
4 3
1 2
2 3
3 1
Output
No

加入题单

上一题 下一题 算法标签: