Block, Stock and Two Smoking Galaxy Notes

Interview

Time limit1sMemory limit512 MB

Summary

Given a graph of effective pairs, pick a techlead and split the rest into singles or pairs such that every pair is an edge and each team has someone adjacent to the techlead.

Level: Medium7 of 10
Topics: Graph, Greedy, Implementation, Brute force
Solved: No attempts yet

Problem

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

All engineers except the techlead must be divided into teams of one or two engineers (recently I read the 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 whether they can interact effectively.

The choice of techlead and the distribution into teams is effective if every two-member team consists of two engineers who can interact effectively, and in every 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 (I am 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 \le n \le 1000$ , $0 \le m \le 10\,000$ ), the number of software engineers and the number of successfully interacting pairs.

Each of the next $m$ lines contains two integers $u\_i$ , $v\_i$ ( $1 \le u\_i, v\_i \le n$ , $u\_i \ne v\_i$ ), the indices of engineers forming an effectively interacting pair.

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 Yes on the first line.

On the second line print two integers $l$ , $k$ ( $1 \le l \le n$ , $\left\lceil \frac{n-1}{2} \right\rceil \leq k \leq n - 1$ ), the index of the techlead and the number of teams.

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

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

Examples3

Example 1
Input
```
5 4
1 2
2 3
3 4
4 5
```
Expected output
```
Yes
3 2
2 1
4 5
```
Example 2
Input
```
4 4
1 2
2 3
3 4
4 1
```
Expected output
```
Yes
1 2
2 3
4 -1
```
Example 3
Input
```
4 3
1 2
2 3
3 1
```
Expected output
```
No
```