Codeforces Round #188 (Div. 1) C. Balance

#include <bits/stdc++.h>

const int N = 305;
const int ME = 2 * 5e4 + 7;
const int M = 2 * N * N;

struct E {
  int v, ne;
} e[ME];
int head[N], cnt = 1, n, v, m;

void add(int u, int v) {
  e[++cnt].v = v; e[cnt].ne = head[u]; head[u] = cnt;
}

int color[N], colorNum;
long long sa[N], sb[N];
int a[N], b[N];

void dfs(int u, int colorIndex) {
  color[u] = colorIndex;
  sa[colorIndex] += a[u];
  sb[colorIndex] += b[u];
  for (int i = head[u]; i; i = e[i].ne) {
    int v = e[i].v;
    if (!color[v])
      dfs(v, colorIndex);
  }
}

bool col() {
  for (int i = 1; i <= n; i++)
    if (!color[i]) dfs(i, ++colorNum);
  for (int i = 1; i <= colorNum; i++)
    if (sa[i] != sb[i]) return 0;
  return 1;
}

int res, ans[M][3], pre[N];
bool vis[N];

void findpath(int st, int ed) {
  std::queue<int> que;
  pre[st] = 0;
  que.push(st);
  memset(vis, 0, sizeof(vis));
  while (!que.empty()) {
    int u = que.front(); que.pop();
    vis[u] = 1;
    if (u == ed) return;
    for (int i = head[u]; i; i = e[i].ne) {
      int v = e[i].v;
      if (vis[v]) continue;
      pre[v] = u;
      que.push(v);
    }
  }
}

void solve(int st, int ed, int need) {
  if (st == ed) return;
  int can = std::min(a[pre[ed]], need);
  ans[res][0] = pre[ed], ans[res][1] = ed, ans[res][2] = can;
  if (can) {
    res++;
    a[pre[ed]] -= can;
    a[ed] += can;
  }
  solve(st, pre[ed], need);
  if (can < need) {
    can = need - can;
    ans[res][0] = pre[ed], ans[res][1] = ed, ans[res][2] = can;
    res++;
    a[pre[ed]] -= can;
    a[ed] += can;
  }
}

int main() {
  scanf("%d%d%d", &n, &v, &m);
  for (int i = 1; i <= n; i++)
    scanf("%d", a + i);
  for (int i = 1; i <= n; i++)
    scanf("%d", b + i);
  for (int i = 1, x, y; i <= m; i++) {
    scanf("%d%d", &x, &y);
    add(x, y); add(y, x);
  }
  if (!col()) {
    puts("NO");
    return 0;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n && a[i] != b[i]; j++) {
      if (color[i] != color[j]) continue;
      if (a[i] > b[i] && a[j] < b[j]) {
        findpath(i, j);
        solve(i, j, std::min(a[i] - b[i], b[j] - a[j]));
      } else if (a[i] < b[i] && a[j] > b[j]) {
        findpath(j, i);
        solve(j, i, std::min(a[j] - b[j], b[i] - a[i]));
      }
    }
  }
  printf("%d\n", res);
  for (int i = 0; i < res; i++)
    printf("%d %d %d\n", ans[i][0], ans[i][1], ans[i][2]);
  return 0;
}