Problem Description

Translated from ROI 2021 D2T2。

Vasya recently came up with a new kind of entertainment. He wants a directed connected graph with $n$ vertices and $2\times(n−1)$ edges to be his toy. This graph satisfies the following condition: for every edge $(u, v)$ in the graph, there is also a reverse edge $(v, u)$. In other words, this graph is obtained from a tree, where each undirected edge is replaced by two directed edges in opposite directions.

Vasya calls such a pair of edges $(e_1, e_2)$ a “gadget” if the endpoint of $e_1$ is the start point of $e_2$, or the endpoint of $e_2$ is the start point of $e_1$ (in particular, two opposite directed edges also form a “gadget”). Simply put, a “gadget” is a path of length $2$. Vasya’s entertainment is to partition all edges of the graph into pairwise disjoint “gadgets”. Of course, for the original graph, this is easy to do.

However, Vasya’s good friend Petya removed $2k$ directed edges from the tree, so that the remaining graph has $m = 2\times (n - 1) - 2\times k$ directed edges.

Now Vasya wants to know whether it is possible to partition the remaining edges into pairwise disjoint “gadgets”. If it is possible, he also wants to find one such partition.

Input Format

The first line contains two integers $n$ and $m$, representing the number of vertices and the number of remaining edges. It is guaranteed that $m$ is even.

The next $m$ lines each contain two integers $u_i$ and $v_i$, indicating a remaining directed edge from $u_i$ to $v_i$.

Output Format

If it is impossible to partition the edges into “gadgets”, output No.

Otherwise, output Yes, and then output $\frac{m}{2}$ lines. Each line contains $4$ numbers, describing the two directed edges in one “gadget”. Each directed edge is described by its start point and endpoint.

5 6
1 2
2 1
1 5
2 3
2 4
4 2

Yes
1 2 2 3
2 1 1 5
2 4 4 2

4 4
2 1
2 3
2 4
4 2

No

4 4
1 2
2 1
3 4
4 3

Yes
1 2 2 1
3 4 4 3

Hint

The “gadget” partition for the first sample is shown in the figure below. Two lines of the same type form one “gadget”.

For $100\%$ of the testdata, $2 \le n \le 150000,2 \le m \le 2\times n - 2,1 \le u_i, v_i \le n$.

Translated by ChatGPT 5