Spaceship Route Construction

You are given a collection of n planets and a list of m forbidden pairs of planets. Your task is to construct a route—a spanning tree connecting all n planets—such that no direct connection (edge) in the route is a forbidden pair. In other words, you must choose n − 1 allowed connections so that every planet is reachable from every other planet, and none of these connections appear in the forbidden list.

A connection between planets u and v is considered forbidden if the unordered pair ({u,v}) appears in the forbidden list. If a valid route exists, output “YES” followed by the list of allowed connections; otherwise, output “NO”.

inputFormat

The first line of input contains two integers n and m, where n is the number of planets and m is the number of forbidden pairs. Each of the next m lines contains two integers u and v, indicating that a direct connection between planets u and v is forbidden.

outputFormat

If a valid route exists, print “YES” on the first line, followed by n − 1 lines each containing two integers representing an allowed connection. If no valid route exists, print “NO”.## sample

3 0

YES
1 2
1 3