Problem: You 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 c1, c2, ..., cn, each of them is between  - n and n, inclusive. It is also guaranteed that the parity of cv 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·n2 and 2·n2 (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 cv, or determine that this is impossible.

Input

The first line contains two integers n and m (2 ≤ n ≤ 105, n - 1 ≤ m ≤ 105) — the number of vertices and the number of edges.

The next line contains n integers c1, c2, ..., cn ( - n ≤ ci ≤ n), where ci is the required sum of weights of edges connected to vertex i. It is guaranteed that the parity of ci 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 ai and bi (1 ≤ ai, bi ≤ n; ai ≠ bi), meaning that the i-th edge connects vertices ai and bi.

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 wi ( - 2·n2 ≤ wi ≤ 2·n2).

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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const int MOD = 1000000007;
const int UNDEF = -1;
const int INF = 1 << 30;
template <typename T>
inline bool chkmax(T &aa, T bb) {
  return aa < bb ? aa = bb, true : false;
}
template <typename T>
inline bool chkmin(T &aa, T bb) {
  return aa > bb ? aa = bb, true : false;
}
int rint();
char rch();
long long rlong();
const int mn = 1e5 + 2;
vector<pair<int, int> > g[mn];
int inp[mn];
char vcol[mn];
int n;
int sodd = -1;
void findodd(int x, int p, int col) {
  if (vcol[x] != -1) {
    if (vcol[x] == col)
      return;
    else {
      sodd = x;
      return;
    }
  }
  vcol[x] = col;
  for (auto &yy : g[x]) {
    int y = yy.first;
    if (y == p) continue;
    findodd(y, x, col ^ 1);
  }
}
vector<int> voddcyc;
bitset<mn> sn[2];
bool getoddcyc(int x, int p, int col) {
  if (sn[col][x]) return false;
  sn[col][x] = true;
  if (x == sodd && col == 1) return true;
  for (auto &yy : g[x]) {
    int y = yy.first;
    if (y == p) continue;
    bool res = getoddcyc(y, x, col ^ 1);
    if (res) {
      voddcyc.push_back(yy.second);
      ;
      return true;
    }
  }
  return false;
}
long long vans[mn];
bitset<mn> seen;
long long dfs(int x, int p) {
  seen[x] = true;
  long long sum = 0;
  for (auto &ye : g[x]) {
    int y = ye.first, e = ye.second;
    if (y == p || seen[y]) continue;
    long long got = dfs(y, x);
    vans[e] += got;
    ;
    sum += got;
  }
  long long need = inp[x] - sum;
  return need;
}
void fail(int t) {
  printf("NO\n");
  exit(0);
}
bool check(int x) {
  long long sum = 0;
  for (auto &ye : g[x]) {
    int e = ye.second;
    sum += vans[e];
  }
  if (sum != inp[x])
    ;
  return sum == inp[x];
}
bool checkall() {
  for (int x = 1; x <= n; x++)
    if (!check(x)) return false;
  return true;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  n = rint();
  int m = rint();
  for (int x = 1; x <= n; x++) inp[x] = rint();
  for (int e = 1; e <= m; e++) {
    int x = rint(), y = rint();
    g[x].push_back(make_pair(y, e));
    g[y].push_back(make_pair(x, e));
  }
  memset(vcol, -1, sizeof vcol);
  findodd(1, -1, 0);
  if (sodd != -1) {
    memset(vcol, -1, sizeof vcol);
    bool res = getoddcyc(sodd, -1, 0);
    voddcyc.size() & 1;
    res;
    dfs(sodd, -1);
    long long extra = 0;
    for (auto &ye : g[sodd]) {
      extra += vans[ye.second];
    }
    long long need = inp[sodd] - extra;
    ;
    long long offset = (need) / 2;
    for (auto &e : voddcyc) {
      vans[e] += offset;
      ;
      offset *= -1;
    }
  } else {
    dfs(1, -1);
  }
  if (!checkall()) fail(3);
  printf("YES\n");
  for (int e = 1; e <= m; e++) printf("%lld\n", vans[e]);
}
static char stdinBuffer[1024];
static char *stdinDataEnd = stdinBuffer + sizeof(stdinBuffer);
static const char *stdinPos = stdinDataEnd;
void readAhead(size_t amount) {
  size_t remaining = stdinDataEnd - stdinPos;
  if (remaining < amount) {
    memmove(stdinBuffer, stdinPos, remaining);
    size_t sz = fread(stdinBuffer + remaining, 1,
                      sizeof(stdinBuffer) - remaining, stdin);
    stdinPos = stdinBuffer;
    stdinDataEnd = stdinBuffer + remaining + sz;
    if (stdinDataEnd != stdinBuffer + sizeof(stdinBuffer)) *stdinDataEnd = 0;
  }
}
int rint() {
  readAhead(32);
  int x = 0;
  bool neg = false;
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  if (*stdinPos == '-') {
    ++stdinPos;
    neg = true;
  }
  while (*stdinPos >= '0' && *stdinPos <= '9') {
    x *= 10;
    x += *stdinPos - '0';
    ++stdinPos;
  }
  return neg ? -x : x;
}
char rch() {
  readAhead(16);
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  char ans = *stdinPos;
  ++stdinPos;
  return ans;
}
long long rlong() {
  readAhead(32);
  long long x = 0;
  bool neg = false;
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  if (*stdinPos == '-') {
    ++stdinPos;
    neg = true;
  }
  while (*stdinPos >= '0' && *stdinPos <= '9') {
    x *= 10;
    x += *stdinPos - '0';
    ++stdinPos;
  }
  return neg ? -x : x;
}