Problem Description

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.

Input Format

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$.

Output Format

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.

7 8
1 2
1 3
2 3
2 6
3 4
5 2
5 7
6 7

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

7 8
1 2
2 3
2 6
4 5
4 7
5 3
7 3
7 6

-1

Hint

[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.

Translated by ChatGPT 5