Description

Please determine whether there exists a tree that satisfies the following conditions. If so, please try to construct it.

The tree contains $n$ vertices numbered from $1$ to $n$. Additionally, $m$ pairs of vertices $(s_i, t_i)$ are given, and it is required that these $m$ paths from vertex $s_i$ to vertex $t_i$ cover each edge exactly once $^\dagger$.

If you correctly determine whether there is a solution but cannot construct the tree, you can still obtain some points. See Scoring Method part for details.

$\dagger$ A path from vertex $s$ to vertex $t$ covers an edge $(u, v)$ if and only if edge $(u, v)$ is on the shortest path from vertex $s$ to vertex $t$.

Input Format

The first line contains two integers $n$ and $m$, representing the number of vertices in the tree and the number of given vertex pairs.

The next $m$ lines each contain two integers $s_i$ and $t_i$, representing a pair of vertex.

Output Format

The first line should output a string "Yes" or "No" (case-insensitive) indicating whether there is a solution.

If there is a solution, continue to output $n-1$ lines, each containing two integers $u_i$ and $v_i$, describing an edge. You need to ensure that $\bm{1 \leq u_i, v_i \leq n}$ and that all edges form a tree.

6 2
1 2
3 4

Yes
1 5
2 5
3 5
4 6
5 6

3 3
1 2
2 3
1 3

No

Hint

Sample Explanation #1

The top left diagram shows the tree given in the sample output. Edges $(1,5)$ and $(5,2)$ are covered by path $(1,2)$, and edges $(3,5)$, $(5,6)$, and $(6,4)$ are covered by path $(3,4)$, which meets the problem requirements.

In the top right diagram, edge $(5,6)$ is covered by both paths $(1,2)$ and $(3,4)$, which does not meet the problem requirements.

In the bottom left diagram, edge $(5,6)$ is not covered by any path, which does not meet the problem requirements.

The bottom right diagram is not a tree, which does not meet the problem requirements.

Sample Explanation #2

It can be proven that there is no tree that meets the requirements.

Scoring Method

This problem uses special judge for evaluation.

For each test case:

• If the first line has the wrong format or does not match the answer (case-insensitive), you will receive $0\%$ of the points.
• If the first line is correct and says "No", you will receive $100\%$ of the points.
• If the first line is correct and says "Yes", but the format of the following $n-1$ lines is incorrect, you will receive $0\%$ of the points. Therefore, please ensure that the output forms a tree.
• If the first line is correct and says "Yes", the format of the following $n-1$ lines is correct, but the tree does not meet the requirements, you will receive $20\%$ of the points.
• If the first line is correct and says "Yes", the format of the following $n-1$ lines is correct, and the tree meets the requirements, you will receive $100\%$ of the points.

That is, for the first sample, on the basis of correctly outputting "Yes", outputting the top left diagram will give full points, outputting the top right and bottom left diagrams will give $20\%$ of the points, and outputting the bottom right diagram will not give any points; for the second sample, correctly outputting "No" will give full points.

Constraints

For all test data, it is guaranteed that:

• $2 \leq n \leq 3 \times 10^5$;
• $1 \leq m \leq 3 \times 10^5$;
• $1 \leq s_i, t_i \leq n$ and $s_i \neq t_i$.

Subtasks are used in this task.

• Subtask 0 (10 points): $n \leq 3$, $m \leq 3$.
• Subtask 1 (10 points): $n \leq 10$, $m \leq 10$.
• Subtask 2 (20 points): $m = 1$.
• Subtask 3 (10 points): $n \leq 300$, $m \leq 300$.
• Subtask 4 (10 points): $n \leq 2 \times 10^3$, $m \leq 2 \times 10^3$.
• Subtask 5 (20 points): $m \leq 2 \times 10^3$.
• Subtask 6 (20 points): No further restrictions.
• Subtask 7 (0 points): Test cases added after the contest.