問題文

頂点が $N$ 個、辺が $M$ 本の連結単純無向グラフ $G$ が与えられます。 $G$ の頂点は頂点 $1, 2, \cdots, N$ 、辺は辺 $1, 2, \cdots, M$ と番号付けられています。辺 $i$ は頂点 $U_i$ と頂点 $V_i$ を結ぶ無向辺です。

また、数列 $A = (A_1,A_2, \cdots, A_N)$ があり、最初はすべて $A_i=0$ に初期化されています。

以下の操作を $i=1,2,\cdots, M$ の順に行います。

• $0$ 以上 $998244353$ 未満の整数 $x_i$ を選び、 $A_{U_i}, A_{V_i}$ の両方に $x_i$ を足す。その後、 $A_{U_i}, A_{V_i}$ をそれぞれ $998244353$ で割った余りに置き換える。

数列 $B = (B_1, B_2, \cdots, B_N)$ が与えられます。操作の結果、数列 $A$ と数列 $B$ が一致するようにすることはできますか？できる場合は、そのような操作を $1$ つ構築してください。

制約

• 入力はすべて整数
• $2 \le N \le 10^5$
• $N-1 \le M \le \min\{10^5, N(N-1)/2\}$
• $1 \le U_i \lt V_i \le N$ $(1 \le i \le M)$
• $(U_i, V_i) \ne (U_j, V_j)$ $(i \ne j)$
• $G$ は連結である。
• $G$ は単純である。すなわち、多重辺や自己ループを含まない。
• $0 \le B_i \lt 998244353$ $(1 \le i \le N)$

入力

$N$ $M$
$B_1$ $B_2$ $\cdots$ $B_N$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_M$ $V_M$

出力

操作の結果 $A=B$ とできる場合、そのような操作の 1 つを、各操作で選んだ $x_i$ を用いて次の形式で出力せよ。

$x_1$ $x_2$ $\cdots$ $x_M$

複数の答えがある場合はどれを出力してもよい。

操作の結果 $A=B$ とできない場合は -1 を出力せよ。

サンプル

3 2
2 1 998244352
1 2
2 3

2 998244352

2 1
998 244
1 2

-1

5 10
2 3 4 5 6
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

5 998244351 4 998244348 1 998244349 1 0 5 5