P9392 Yellow Rose.

Given a simple directed acyclic graph $G$ with $n$ vertices. The vertex weight of vertex $i$ is defined as $w_i$, but **the vertex weights are not given**. You need to construct a directed acyclic graph $G'$ with at most $2\times n$ vertices and exactly $n$ edges. For each edge in $G'$, you must assign some $w_i$ as its edge weight, such that the length of the **longest path** in $G'$ is equal to that in $G$. In $G$, the length of a path is defined as the sum of the weights of all vertices on the path. In $G'$, it is defined as the sum of the weights of all edges on the path. However, none of the $w_i$ are given, so your construction of $G'$ must satisfy: for any possible **positive** sequence $[w_1,\ldots,w_n]$, the longest path lengths of $G$ and $G'$ must be equal. Construct such a $G'$, or state that it does not exist.

The first line contains two integers $n,m$. The next $m$ lines each contain two integers $x,y$, indicating that there is a directed edge from vertex $x$ to vertex $y$.

If there is no $G'$ satisfying the requirements, output one line containing $-1$. Otherwise, output $n+1$ lines: The first line contains an integer $N$, the number of vertices in your constructed graph $G'$. The next $n$ lines each contain three integers $x,y,z$, indicating that in $G'$ there is an edge from vertex $x$ to vertex $y$, and its edge weight equals $w_z$. You must ensure that $0\leq N\leq 2\times n$, $1\leq x,y\leq N$, and $1\leq z\leq n$. If there are multiple valid solutions, you may output any one of them.

**[Sample #1 Explanation]** In the figure below, the left is $G$ and the right is $G'$. Vertices/edges with the same color indicate the same weight:  Note that this is only one possible answer. Other correct answers can also be accepted. --- **[Sample #2 Explanation]** In the figure below is $G$. There is no valid $G'$:  --- **[Constraints]** For all testdata: $1\leq n\leq 20000$, $1\leq m\leq 3\times 10^5$, $1\leq x,y\leq n$. The given graph is guaranteed to be acyclic and has no multiple edges. | Subtask ID | $n\leq$ | $m\leq$ | Special Property | Score | | :----------------: | :-----: | :------------: | :----------------------------: | :---: | | $\text{Subtask 1}$ | $5000$ | $4999$ | $m=n-1$, each vertex has indegree at most $1$ | $18$ | | $\text{Subtask 2}$ | $5000$ | $4999$ | $m=n-1$, each vertex has outdegree at most $1$ | $19$ | | $\text{Subtask 3}$ | $20$ | $50$ | None | $20$ | | $\text{Subtask 4}$ | $5000$ | $10000$ | None | $21$ | | $\text{Subtask 5}$ | $20000$ | $3\times 10^5$ | None | $22$ | ---  Translated by ChatGPT 5