Gadget Partition

Vasya has a graph with n vertices and m edges. The edges given are the remaining edges after some previous operations. Vasya wonders whether it is possible to partition all of these remaining edges into pairwise disjoint gadgets. A gadget is defined as a pair of distinct edges that share a common vertex. In other words, if two edges (u, v) and (u, w) (or with u replaced by any common vertex) are chosen, then they form a gadget with u as the common vertex.

If such a partition exists then every edge must belong to exactly one gadget; note that this immediately implies that m must be even. Your task is to determine whether such a partition exists and, if so, to output one valid partition.

Output format details:

• If a valid partition exists, print YES in the first line. Then print m/2 lines, each containing three integers: the common vertex v and the other two endpoints a and b such that the gadget consists of edges (v, a) and (v, b). The order of gadgets and the order of endpoints in each gadget do not matter.
• If a partition does not exist, simply print NO.

The correctness of the partition is guaranteed if each edge in the input is used exactly once in one gadget and within every gadget the two edges share a common vertex.

The underlying approach can be thought of as a greedy pairing: for each vertex, try to pair up any two unused edges incident to it. Since each edge appears in two vertex lists, a proper ordering (for example, processing vertices from 1 to n) will yield a valid solution whenever one exists.

The formulas used are in LaTeX: For any pair of edges incident to vertex \(v\), if the edges are \((v, a)\) and \((v, b)\), then they form a gadget.

inputFormat

The first line contains two integers n and m, representing the number of vertices and the number of edges respectively. It is guaranteed that \(1 \le n \le 10^5\) and \(0 \le m \le 10^5\).

Each of the following m lines contains two integers u and v (\(1\le u,v\le n\), \(u \neq v\)) indicating an edge between vertices u and v. Note that the graph is undirected and the given edges are the remaining edges.

outputFormat

If a partition into gadgets exists, print YES on the first line. Then, print m/2 lines; each line must contain three integers: v a b denoting that the two edges \((v,a)\) and \((v,b)\) form a gadget. If no valid partition exists, print NO.

sample

3 2
1 2
2 3

YES
2 1 3