Background

The problem title means: See you next year.

Xiao R is a high school senior. During the summer break before her senior year, she reviewed the essay The Biography of Guo Tuo the Camel-Grower, and subsequently created this tree-related problem.

After submitting this problem to the problem-setting team, she decided to devote all her time and energy to her journey toward the Gaokao, looking forward to meeting everyone again in the algorithm competitions in the summer of 2025.

Description

Determine whether there exists a tree that satisfies the following conditions. If it exists, provide a construction.

The tree contains $n$ nodes, labeled $1 \sim n$. Additionally, you are given $m$ pairs of points $(s_i, t_i)$, and it is required that the $m$ paths from $s_i$ to $t_i$ in the tree cover every edge exactly once $^\dagger$.

If you correctly determine whether a solution exists but cannot construct the tree, you can still receive partial points; see [Scoring] for details.

$\dagger$ A path from point $s$ to point $t$ is said to cover an edge $(u, v)$ if and only if the edge $(u, v)$ lies on the shortest path between $s$ and $t$.

Input

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

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

Output

The first line should output a string Yes or No (case-insensitive), indicating whether a solution exists.

If a solution exists, output $n-1$ additional lines, each containing two integers $u_i$ and $v_i$, describing an edge. You must ensure that $1 \le u_i, v_i \le n$ and that all edges form a tree.

Examples

Input 1

6 2
1 2
3 4

Output 1

Yes
1 5
2 5
3 5
4 6
5 6

Note 1

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

In the top-right figure, the edge $(5,6)$ is covered by both path $(1,2)$ and path $(3,4)$, which does not satisfy the requirements.

In the bottom-left figure, the edge $(5,6)$ is not covered by any path, which does not satisfy the requirements.

The bottom-right figure is not a tree, which does not satisfy the requirements.

Input 2

3 3
1 2
2 3
1 3

Output 2

No

Note 2

It can be proven that no such tree exists.

Scoring

This problem uses a custom checker (Special Judge) for evaluation.

For each test case:

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

In other words, for the first sample, given a correct Yes, outputting the top-left figure yields full marks, outputting the top-right or bottom-left figures yields $20\%$ of the points, and outputting the bottom-right figure yields no points. For the second sample, outputting the correct No yields full marks.

Constraints

For all test data, it is guaranteed that:

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

This problem uses bundled testing.

• Subtask 1 (10 points): $n \le 3$, $m \le 3$.
• Subtask 2 (10 points): $n \le 10$, $m \le 10$.
• Subtask 3 (20 points): $m = 1$.
• Subtask 4 (10 points): $n \le 300$, $m \le 300$.
• Subtask 5 (10 points): $n \le 2 \times 10^3$, $m \le 2 \times 10^3$.
• Subtask 6 (20 points): $m \le 2 \times 10^3$.
• Subtask 7 (20 points): No special restrictions.