Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Weighting a Tree

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given a connected undirected graph with *n* vertices and *m* edges. The vertices are enumerated from 1 to *n*.

You are given *n* integers *c* _{1}, *c* _{2}, ..., *c* _{ n}, each of them is between - *n* and *n*, inclusive. It is also guaranteed that the parity of *c* _{ v} equals the parity of degree of vertex *v*. The degree of a vertex is the number of edges connected to it.

You are to write a weight between - 2·*n* ^{2} and 2·*n* ^{2} (inclusive) on each edge in such a way, that for each vertex *v* the sum of weights on edges connected to this vertex is equal to *c* _{ v}, or determine that this is impossible.

Input

The first line contains two integers *n* and *m* (2 ≤ *n* ≤ 10^{5}, *n* - 1 ≤ *m* ≤ 10^{5}) — the number of vertices and the number of edges.

The next line contains *n* integers *c* _{1}, *c* _{2}, ..., *c* _{ n} ( - *n* ≤ *c* _{ i} ≤ *n*), where *c* _{ i} is the required sum of weights of edges connected to vertex *i*. It is guaranteed that the parity of *c* _{ i} equals the parity of degree of vertex *i*.

The next *m* lines describe edges of the graph. The *i*-th of these lines contains two integers *a* _{ i} and *b* _{ i} (1 ≤ *a* _{ i}, *b* _{ i} ≤ *n*; *a* _{ i} ≠ *b* _{ i}), meaning that the *i*-th edge connects vertices *a* _{ i} and *b* _{ i}.

It is guaranteed that the given graph is connected and does not contain loops and multiple edges.

Output

If there is no solution, print "NO".

Otherwise print "YES" and then *m* lines, the *i*-th of them is the weight of the *i*-th edge *w* _{ i} ( - 2·*n* ^{2} ≤ *w* _{ i} ≤ 2·*n* ^{2}).

Examples

Input

3 3

2 2 2

1 2

2 3

1 3

Output

YES

1

1

1

Input

4 3

-1 0 2 1

1 2

2 3

3 4

Output

YES

-1

1

1

Input

6 6

3 5 5 5 1 5

1 4

3 2

4 3

4 5

3 5

5 6

Output

YES

3

5

3

-1

-3

5

Input

4 4

4 4 2 4

1 2

2 3

3 4

4 1

Output

NO

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/08/2020 07:45:17 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|