Edge-Disjoint Tree Path Partition

You are given an integer n (the number of nodes, labeled 1 through n) and an integer m followed by m pairs of integers (s_i, t_i). The task is to decide whether there exists a tree on n nodes along with an assignment of m paths (one from s_i to t_i for each pair) such that every edge of the tree is covered exactly once by these paths.

The path from s to t in the tree is defined to be the unique shortest simple path (which is well‐defined since a tree does not contain cycles). An edge (u,v) is said to be covered by the path from s to t if and only if (u,v) lies on that unique shortest path.

Note: It is allowed to decide correctly whether a valid tree exists even if you are unable to provide an explicit construction. (Partial credit may be awarded in that case.)

Problem Constraints and Observations:

• The tree has exactly n-1 edges.
• Each non‐trivial query (where s_i ≠ t_i) will cover at least one edge. Thus, if we let k be the number of non‐trivial queries, a necessary condition is that k ≤ n-1 (since the total number of edges that must be covered is n-1).
• The queries together must partition the edge–set of the tree. In other words, if a tree exists satisfying the requirements, the sum of the lengths (in edges) of the m query paths must be exactly n-1 and the paths must be edge–disjoint.
• A query with s_i = t_i is considered trivial and covers no edge.

Input/Output Format:

inputFormat

The first line contains two integers n and m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 10⁵). Each of the following m lines contains two integers s_i and t_i (1 ≤ s_i, t_i ≤ n).

outputFormat

If there exists a tree on n nodes along with an assignment of m paths covering each edge exactly once (as specified above), output YES on the first line. Then, if you wish, you may output a valid construction of the tree in the following n-1 lines (each line containing two integers indicating an edge). Otherwise, if no such tree exists, output NO.

Note: A correct decision (YES/NO) will receive partial score even if the tree is not constructed.

sample

1 0

YES