Cactus Transformation

In the university, Caroline started to learn about cactus graphs. Her teacher wanted to check whether the students really understood the definition of a cactus, so he gave them the following home assignment.

You are given two cactuses with the same number of vertices and edges. Determine whether the first cactus can be transformed into the second one using the following two-step operation at most $15\,000$ times:

• Pick an arbitrary edge from the first cactus and remove it. After this step, the graph does not have to be a cactus.
• Add an arbitrary non-existing edge to the first graph so that the graph becomes a cactus.

Each operation consists of both steps, so you must perform both steps every time.

It is guaranteed that if the transformation is possible, it can be done using at most $15\,000$ operations.

A cactus is a connected undirected graph in which every edge lies on at most one simple cycle. A cactus has no multiple edges and no loops.

Two cactuses are called the same if for every pair of vertices $v$ and $u$ ($1 \le v < u \le n$), either both cactuses have the edge $(v, u)$ or neither does.

The first line contains two integers $n$ and $m$ ($3 \le n \le 1000$, $n - 1 \le m \le \lfloor \frac{3(n - 1)}{2} \rfloor$), the number of vertices and edges in each cactus. Each of the next $2 \cdot m$ lines contains two integers $u$ and $v$ ($1 \le u \ne v \le n$), an edge. The first $m$ lines describe the first cactus, and the next $m$ lines describe the second cactus.

If the first cactus cannot be transformed into the second one, print a single line with "NO".

Otherwise, print "YES" on the first line. On the second line, print the number of operations $c$ ($0 \le c \le 15\,000$). Each of the following $c$ lines contains four integers $w_1$, $w_2$, $w_3$, $w_4$ ($1 \le w_i \le n$). The vertices $w_1$ and $w_2$ are the endpoints of the removed edge, and $w_3$ and $w_4$ are the endpoints of the added edge.