2684. 「BalticOI 2013」管道 Pipes

题目描述

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

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

输入格式

第一行：水库数量 $n$，管道数量 $m$（$1 \le n \le 100\,000$, $1 \le m \le 500\,000$）。

下面 $n$ 行：第 $i$ 个水库的变化速度 $c_i$（$-10^9 \le c_i \le 10^9$）。

接下来 $m$ 行：$(u, v)$，保证没有重边。

输出格式

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

样例 1

输入

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

输出

2
-6
2

样例 2

输入

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

输出

0

数据范围与提示

• $1 \le n \le 10^5$
• $1 \le m \le 5 \times 10^5$
• $-10^9 \le c_i \le 10^9$
• 如果方案唯一，$-10^9 \le x_i \le 10^9$
• 对于 $30\%$ 的测试数据，水库为树结构