题目描述

小Z手上有一个 $n$ 个点、$m$ 个边的无向图。每个节点有一个权值 $a_i$。

小Z的任务是为图中的每条边 $j\left(1 \le j \le m\right)$ 分配一个非负整数边权 $w_j$，使得该图满足以下条件：
$\hspace{23pt}\bullet\,$至少存在一个顶点 $s\left(1 \le s \le n\right)$，使得对于图中的任意顶点 $i\left(1 \le i \le n\right)$，都有从顶点 $s$ 到顶点 $i$ 的最短路径长度恰好等于 $a_i$。

若存在满足条件的边权分配方案，请输出每条边的权值；否则输出 $\texttt{-1}$。

输入格式

第一行包含两个正整数 $n$ 和 $m$，代表图的顶点数和边数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，代表每个顶点的权值。

接下来 $m$ 行，每行包含两个正整数 $u_j, v_j\left(1 \le u_j, v_j \le n, u_j \neq v_j\right)$，代表第 $j$ 条边连接的两个顶点（保证没有重边、自环）。

输出格式

若存在满足条件的分配方案，输出 $m$ 行，每行一个整数，第 $j$ 行的整数代表第 $j$ 条边的权值 $w_j\left(0 \le w_j \le 10^9\right)$。如果有多组解，输出任意一组即可。

若不存在满足条件的方案，输出 $\texttt{-1}$。

输入输出样例

3 3
0 2 3
1 2
2 3
1 3

2
3
3

样例 $\tt \#1$说明

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

-1

数据范围

$2 \le n \le 2 \times 10^5,n-1 \le m \le 2 \times 10^5$

$0 \le a_i \le 10^9$