← 返回题目列表

Codeforces · 317/C

C. 平衡

中文机器翻译题面 查看原题

给出了一个由 n 个装有水的容器组成的系统。几对血管通过带有输血机制的管子连接。人们可以在由这种管子连接的两个容器之间传输整数升的水(管子在两个方向上工作)。两个容器之间可能有多个管子。管总数等于 e。每个容器的体积等于 v 升。当然,输液过程中任何器皿中的水量不能超过v升。

给定容器中水的初始量 ai 和所需量 bi 找到处理该任务的输血序列。输血总数不得超过2·n2。

输入

输入的第一行包含整数 n、v、e (1 ≤ n ≤ 300, 1 ≤ v ≤ 109, 0 ≤ e ≤ 50000)。

接下来两行各包含 n 个整数:初始 ai 和相应容器中所需的水量 bi (0 ≤ ai, bi ≤ v)。

接下来的 e 行分别以 x y (1 ≤ x, y ≤ n, x ≠ y) 的格式描述一根管子,该管子位于编号为 x 和 y 的容器之间。两个容器之间可能有多个管子。您可能会假设船只以某种方式从 1 到 n 编号。

输出

如果这样的输血序列不存在,则打印“NO”(不带引号)。

否则按以下格式打印任何合适的序列。第一行打印输血总数k(k不应超过2·n2)。在下面的 k 行中,以 x y d 的格式打印输血(从容器编号 x 到容器编号 y 的输血量为 d 升,x 和 y 必须不同)。对于所有输血,d 必须是非负整数。

示例

输入 #1

2 10 1
1 9
5 5
1 2

输出 #1

1
2 1 4

输入 #2

2 10 0
5 2
4 2

输出 #2

NO

输入 #3

2 10 0
4 2
4 2

输出 #3

0