题目描述

给定一个 $N$ 点 $M$ 边的无向图，保证图连通。现在每个点都有一定量的水，现在可以在一条边上进行操作：

• 让水流出：给定 $d$，假设长度为 $m$，流的时间为 $s$，那么总共失水速度为 $\dfrac{2dm^3}{s}$，这条边两边的每个点的失水速度为 $\dfrac{dm^3}{s}$。
• 让水流进：给定 $p$，假设长度为 $m$，流的时间为 $s$，那么总共得水速度为 $\dfrac{2pm^3}{s}$，这条边两边的每个点的得水速度为 $\dfrac{pm^3}{s}$。

现在给定这个图，和每个点的水量的变化速度，求每条边的水量的变化速度的构造方案。

输入格式

第一行两个整数 $N,M$ 代表点数和边数。
这 $N$ 个点编号为 $1$ 到 $N$。
接下来 $N$ 行每行一个整数 $c_i$ 代表这个点的水量变化速度，正数为得水，负数为失水。
接下来 $M$ 行每行两个整数代表一条边。

输出格式

如果不存在这样的构造方案或者有多解，只输出一个整数 0。
如果存在这样的方案，输出 $M$ 行，每行一个整数代表每条边的水量变化速度。
得水为正数，失水为负数。

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 1
1 3

0

提示

数据规模与约定

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$1 \le M \le 5 \times 10^5$，$-10^9 \le c_i \le 10^9$，如果有解且唯一解，每个答案在 $[-10^9,10^9]$ 的范围内。
对于其中 $30\%$ 的数据，该图为一棵树。

说明

翻译自 BalticOI 2013 Day1 C Pipes。