CF317C.Balance

A system of n vessels with water is given. Several pairs of vessels are connected by tubes with transfusion mechanisms. One may transfer an integer amount of liters of water between two vessels connected by such tube (tube works in both directions). There might be multiple tubes between two vessels. Total number of tubes equals e. Volume of each vessel equals v liters. Of course, the amount of the water in any vessel cannot exceed v liters in the process of transfusions.

Given the initial amounts a__i of water in the vessels and the desired amounts b__i find a sequence of transfusions that deals with the task. Total number of transfusions must not exceed 2·_n_2.

给定一个包含 n 个装有水的容器的系统。若干对容器之间通过带有输运机构的管道相互连接。对于任意一对由此类管道连接的容器，均可在二者之间双向传输整数升的水量（管道为双向）。两个容器之间可能存在多条管道。管道总数为 e。每个容器的容积均为 v 升。当然，在输运过程中，任一容器内的水量均不得超过 v 升。

已知各容器的初始水量 a__i 和目标水量 b__i，请找出一组输运操作序列以完成该任务。输运操作的总次数不得超过 $2 \cdot n^2$。

First line of the input contains integers n, v, e (1 ≤ n ≤ 300, 1 ≤ v ≤ 109, 0 ≤ e ≤ 50000).

Next two lines contain n integers each: initial a__i and the desired amounts b__i of water in corresponding vessels (0 ≤ a__i, b__i ≤ v).

Next e lines describe one tube each in the format x y (1 ≤ x, y ≤ n, x ≠ y) for a tube between vessels number x and y. There might be multiple tubes between two vessels. You may assume that vessels are numbered from 1 to n in some way.

输入的第一行包含三个整数 $n$、$v$、$e$（$1 ≤ n ≤ 300$，$1 ≤ v ≤ 10^9$，$0 ≤ e ≤ 50000$）。

接下来两行每行包含 $n$ 个整数：第一行为各容器初始水量 $a_i$，第二行为各容器目标水量 $b_i$（$0 ≤ a_i,\,b_i ≤ v$）。

接下来 $e$ 行，每行描述一根管道，格式为 $x\ y$（$1 ≤ x,\,y ≤ n$，且 $x ≠ y$），表示在编号为 $x$ 和 $y$ 的容器之间存在一根管道。两个容器之间可能存在多根管道。你可以假设容器编号为 $1$ 到 $n$。

Print "NO" (without quotes), if such sequence of transfusions does not exist.

Otherwise print any suitable sequence in the following format. On the first line print the total number of transfusions k (k should not exceed 2·_n_2). In the following k lines print transfusions in the format x y d (transfusion of d liters from the vessel number x to the vessel number y, x and y must be distinct). For all transfusions d must be a non-negative integer.

如果不存在这样的倾倒序列，则输出 "NO"（不带引号）。

否则，按以下格式输出任意一个可行的序列：第一行输出倾倒操作的总次数 $k$（要求 $k$ 不超过 $2\cdot n^2$）；接下来的 $k$ 行每行输出一个倾倒操作，格式为 $x\ y\ d$（表示从编号为 $x$ 的容器向编号为 $y$ 的容器倾倒 $d$ 升液体，其中 $x$ 与 $y$ 必须不同）。所有倾倒操作中的 $d$ 均必须为非负整数。