题目描述

有 $n$ 个水库， $m$ 条管道。Jester 会在某些管道中间凿开一个洞，让水流出来或者用水泵把水打进去。保证这个流速是偶数。对于一条管道 $(u, v)$，如果在中间凿开了一个洞让水流出来，流速是 $2d\rm {m^3}/{s}$，那么水库 $u$ 和 $v$ 失水速度为 $d\rm {m^3}/s$。同理，如果往一条管道 $(u, v)$ 注水，流速为 $2p\rm {m^3}/{s}$，那么 $u$ 和 $v$ 得到水的速度是 $p\rm {m^3}/{s}$。

给定图的构造以及每个水库的水流的变化，问每条边的方案是否唯一。

输入格式

第一行两个正整数 $n,m$。

下面 $n$ 行，每行一个整数，表示第 $i$ 个水库的变化速度 $c_i$。

接下来 $m$ 行，每行两个整数 $u, v$，表示一条连边，保证没有重边。

输出格式

如果方案唯一，输出方案，每行一个数 $x_i$ 表示第 $i$ 条管道的流量变化。放水为负数，灌水为正数。否则输出 $0$。

4 3
-1
1
-3
1
1 2
1 3
1 4

2
-6
2

4 5
1
2
1
2
1 2
2 3
3 4
4 11 3

0

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le m \le 5 \times 10^5$，$-10^9 \le c_i,x_i\le 10^9$。

题目来源

abcdabcd987 提供