{"raw_statement":[{"iden":"statement","content":"给定一张包含 $n$ 个点的简单有向无环图 $G$，点 $i$ 的点权设为 $w_i$，但**点权不是给定的**。\n\n你需要构造一个包含至多 $2\\times n$ 个点和恰好 $n$ 条边的有向无环图 $G'$，你需要为 $G'$ 的每条边钦定某个 $w_i$ 作为它的边权，使得 $G'$ 和 $G$ 的**最长路**长度相等。\n\n在 $G$ 中一条路径的长度定义为其中所有点权和，$G'$ 中则为所有边权和。\n\n然而，所有 $w_i$ 都不是给定的，所以你构造的 $G'$ 需要满足：对于任何一种可能的**正数**序列 $[w_1,\\ldots,w_n]$，$G$ 和 $G'$ 的最长路长度都要相等。\n\n请构造 $G'$，或说明它不存在。"},{"iden":"input","content":"第一行：两个整数 $n,m$。\n\n接下来 $m$ 行：每行两个整数 $x,y$，表示存在一条点 $x$ 到点 $y$ 的有向边。"},{"iden":"output","content":"如果不存在满足题意的 $G'$，则输出一行一个 $-1$。\n\n否则，输出 $n+1$ 行：\n\n第一行：一个整数 $N$，表示你构造的 $G'$ 的点数。\n\n接下来 $n$ 行：每行三个整数 $x,y,z$，表示 $G'$ 中存在一条点 $x$ 到点 $y$ 的边，边权等于 $w_z$。\n\n你需要保证 $0\\leq N\\leq 2\\times n$，$1\\leq x,y\\leq N$，$1\\leq z\\leq n$。\n\n若有多种可能的解，任意输出一个即可。"},{"iden":"note","content":"**【样例 #1 解释】**\n\n如下图，左为 $G$，右为 $G'$，颜色相同的点/边表示权值相同：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/i0wuxctf.png)\n\n注意这只是一种可能的答案，其他正确的答案也可通过。\n\n---\n\n**【样例 #2 解释】**\n\n下图为 $G$，不存在合法的 $G'$：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/tek49neu.png)\n\n---\n\n**【数据范围】**\n\n对于全部数据：$1\\leq n\\leq 20000$，$1\\leq m\\leq 3\\times 10^5$，$1\\leq x,y\\leq n$，保证给定的图无环且无重边。\n\n|     子任务编号     | $n\\leq$ |    $m\\leq$     |           特殊性质            | 分值 |\n| :----------------: | :-----: | :------------: | :---------------------------: | :--: |\n| $\\text{Subtask 1}$ | $5000$  |     $4999$     | $m=n-1$，每个点入度不超过 $1$ | $18$ |\n| $\\text{Subtask 2}$ | $5000$  |     $4999$     | $m=n-1$，每个点出度不超过 $1$ | $19$ |\n| $\\text{Subtask 3}$ |  $20$   |      $50$      |              无               | $20$ |\n| $\\text{Subtask 4}$ | $5000$  |    $10000$     |              无               | $21$ |\n| $\\text{Subtask 5}$ | $20000$ | $3\\times 10^5$ |              无               | $22$ |\n\n---\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/jepg6g1u.png)"}],"translated_statement":null,"sample_group":[["7 8\n1 2\n1 3\n2 3\n2 6\n3 4\n5 2\n5 7\n6 7\n","7\n1 2 1\n1 2 5\n2 3 2\n3 4 3\n3 5 6\n4 6 4\n5 7 7\n"],["7 8\n1 2\n2 3\n2 6\n4 5\n4 7\n5 3\n7 3\n7 6\n","-1\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}