题目描述

给定一张包含 $n$ 个点的简单有向无环图 $G$，点 $i$ 的点权设为 $w_i$，但点权不是给定的。

你需要构造一个包含至多 $2\times n$ 个点和恰好 $n$ 条边的有向无环图 $G'$，你需要为 $G'$ 的每条边钦定某个 $w_i$ 作为它的边权，使得 $G'$ 和 $G$ 的最长路长度相等。

在 $G$ 中一条路径的长度定义为其中所有点权和，$G'$ 中则为所有边权和。

然而，所有 $w_i$ 都不是给定的，所以你构造的 $G'$ 需要满足：对于任何一种可能的正数序列 $[w_1,\ldots,w_n]$，$G$ 和 $G'$ 的最长路长度都要相等。

请构造 $G'$，或说明它不存在。

输入格式

第一行：两个整数 $n,m$。

接下来 $m$ 行：每行两个整数 $x,y$，表示存在一条点 $x$ 到点 $y$ 的有向边。

输出格式

如果不存在满足题意的 $G'$，则输出一行一个 $-1$。

否则，输出 $n+1$ 行：

第一行：一个整数 $N$，表示你构造的 $G'$ 的点数。

接下来 $n$ 行：每行三个整数 $x,y,z$，表示 $G'$ 中存在一条点 $x$ 到点 $y$ 的边，边权等于 $w_z$。

你需要保证 $0\leq N\leq 2\times n$，$1\leq x,y\leq N$，$1\leq z\leq n$。

若有多种可能的解，任意输出一个即可。

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

提示

【样例 #1 解释】

如下图，左为 $G$，右为 $G'$，颜色相同的点/边表示权值相同：

注意这只是一种可能的答案，其他正确的答案也可通过。

---

【样例 #2 解释】

下图为 $G$，不存在合法的 $G'$：

---

【数据范围】

对于全部数据：$1\leq n\leq 20000$，$1\leq m\leq 3\times 10^5$，$1\leq x,y\leq n$，保证给定的图无环且无重边。

子任务编号	$n\leq$	$m\leq$	特殊性质	分值
$\text{Subtask 1}$	$5000$	$4999$	$m=n-1$，每个点入度不超过 $1$	$18$
$\text{Subtask 2}$			$m=n-1$，每个点出度不超过 $1$	$19$
$\text{Subtask 3}$	$20$	$50$	无	$20$
$\text{Subtask 4}$	$5000$	$10000$		$21$
$\text{Subtask 5}$	$20000$	$3\times 10^5$		$22$

---