{"raw_statement":[{"iden":"background","content":"Day 1 Problem D.\n\n题面译自 [EGOI2023 bikesvscars](https://egoi23.se/assets/tasks/day1/bikesvscars.pdf)。\n\n[![CC BY-SA 3.0](https://licensebuttons.net/l/by-sa/3.0/80x15.png)](https://creativecommons.org/licenses/by-sa/3.0/)"},{"iden":"statement","content":"在隆德，骑自行车是一种常见的交通方式，但有时狭窄的街道难以容纳汽车和自行车通行。为了改善这一状况，当地政$ $府希望完全重新设计当地的街道网络。\n\n隆德共有 $N$ 个关键位置（编号从 $0$ 到 $N-1$），人们常常在其间通行。人们通过一条路径在两地之间通行，其中路径是一系列的街道，从第一个地点到另一个。一种交通工具（车或自行车）可以在一条路径上通行，当且仅当经过的所有街道都至少与它一样宽。每个新修的街道连接关键位置其中之二，有着宽度 $W$。这个宽度可以被任意分割为自行车道和机动车道。在隆德，一些工程师最近发明了宽度为 $0$ 的车和自行车（它们可以在宽度为 $0$ 的道路通行）。\n\n这些工程师测量了城市中车和自行车的宽度。对于每一对关键位置，他们知道其间通行的最宽的车和最宽的自行车的宽度，但政$ $府还要求更宽的车和自行车不能在其间通行。\n\n形式化地，对于任意 $i,j$（$0\\le i < j\\le N-1$），你都知道两个整数 $C_{i,j}$ 和 $B_{i,j}$。你的任务是构造一个街道网络连接这 $N$ 个位置。街道的宽度均为 $W$，但对于任意街道 $s$，你可以选择它的自行车道宽度 $b_s$ 和机动车道宽度 $W-b_s$。这个网络必须满足以下要求：\n\n- 必须可以在任意两个位置间通行。这可能需要一辆宽度为 $0$ 的自行车或车。\n- 对于每一对位置 $i,j$（其中 $i < j$），可以只借助宽度至少为 $C_{i,j}$ 的机动车道，在 $i,j$ 间通行。同时，$C_{i,j}$ 是最大的有这一性质的数。这意味着，对于所有 $i,j$ 间的路径，必须满足至少一条街道的机动车道宽度不超过 $C_{i,j}$。\n- 对于每一对位置 $i,j$（其中 $i < j$），可以只借助宽度至少为 $B_{i,j}$ 的自行车道，在 $i,j$ 间通行。同时，$B_{i,j}$ 是最大的有这一性质的数。\n\n你能帮隆德政$ $府设计一个这样的街道网络吗？因为预算有限，你可以修建至多 $2023$ 条街道。你可以在同一对关键位置间修建多条街道，但你不能修建一条连接自己和自己的街道。所有街道都是双向的。"},{"iden":"input","content":"第一行两个整数 $N,W$，表示关键位置数量和街道宽度。\n\n接下来 $N-1$ 行包含 $C_{i,j}$。其中的第 $j$ 行包含所有满足 $i < j$ 的 $C_{i,j}$。因此第一行只会包含 $C_{0,1}$，第二行包含 $C_{0,2}$ 和 $C_{1,2}$，第三行包含 $C_{0,3},C_{1,3},C_{2,3}$，以此类推。\n\n接下来 $N-1$ 行包含 $B_{i,j}$，格式同 $C_{i,j}$。"},{"iden":"output","content":"如果不存在符合要求的街道网络，输出 `NO`。\n\n否则，第一行一个整数 $M$，表示你修建的街道数。\n\n接下来 $M$ 行，每行三个整数 $u,v,b$，表示一条自行车道宽度为 $b$（机动车道宽度为 $W-b$）的连接 $u,v$ 的街道。\n\n你可以使用至多 $2023$ 条街道。你输出的街道必须满足 $0\\le b\\le W$，$0\\le u,v\\le N-1$ 且 $u\\ne v$。你可以在同一对关键位置间使用多条街道（可以有不同的自行车道宽度）。\n\n如果有多解，你可以输出任意一个。"},{"iden":"note","content":"**样例 $1$ 解释**\n\n在样例 $1$ 中，街道的宽度为 $1$，我们需要宽度至少为 $1$ 的自行车道和机动车道各一条连接 $0,1$。解决方案是用两条分开的街道连接，一条自行车道宽度为 $1$，另一条机动车道宽度为 $1$。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/9cbqwrvu.png)\n\n---\n\n**样例 $2$ 解释**\n\n在样例 $2$ 中，街道的宽度依然是 $1$，需要有一条宽度为 $1$ 的自行车道连接任意两个关键位置，且有宽度为 $1$ 的机动车道连接 $1,2$ 和 $2,3$。这与 $C_{1,3}=0$ 矛盾，不应该有宽度为 $1$ 的从 $1$ 到 $3$ 的机动车道，而我们可以合并两条先前提到的路径组成这样一条路径。因此不可能构造出一个符合要求的街道网络。\n\n---\n\n**样例 $3$ 解释**\n\n在样例 $3$ 中，下图的街道网络满足所有要求。例如，应该有一条宽度为 $1=C_{0,5}$ 的机动车道在 $0,5$ 之间（路径 $0\\to 2\\to 4\\to 5$），一条宽度为 $3=B_{0,5}$ 的自行车道在 $0,5$ 之间（路径 $0\\to 3\\to 4\\to 5$）。同时，可以验证，不存在路径有着更大的宽度下限。注意样例 $3$ 可能有很多其他解法。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/p8dwhz4s.png)\n\n---\n\n**数据范围**\n\n对于全部数据，$2\\le N\\le 500$，$1\\le W\\le 10^6$，$0\\le C_{i,j},B_{i,j}\\le W$。\n\n- 子任务一（$10$ 分）：所有 $C_{i,j}$ 都相同，所有 $B_{i,j}$ 都相同，$N\\le 40$。\n- 子任务二（$5$ 分）：所有 $C_{i,j}$ 都相同，所有 $B_{i,j}$ 都相同。\n- 子任务三（$17$ 分）：$N\\le 40$。\n- 子任务四（$18$ 分）：$W=1$。\n- 子任务五（$19$ 分）：所有 $B_{i,j}$ 都相同。\n- 子任务六（$31$ 分）：无特殊限制。"}],"translated_statement":null,"sample_group":[["2 1\n1\n1","2\n0 1 0\n0 1 1"],["4 1\n0\n0 1\n0 0 1\n1\n1 1\n1 1 1","NO"],["6 6\n5\n4 4\n1 1 1\n1 1 1 3\n1 1 1 5 3\n2\n3 2\n6 2 3\n3 2 5 3\n3 2 4 3 4","8\n0 1 1\n0 2 3\n1 2 2\n0 3 6\n2 4 5\n3 4 3\n3 5 1\n4 5 4"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}