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>
using namespace std;
template <typename... As>
struct tpl : public std::tuple<As...> {
  using std::tuple<As...>::tuple;
  tpl() {}
  tpl(std::tuple<As...> const& b) { std::tuple<As...>::operator=(b); }
  template <typename T = tuple<As...> >
  typename tuple_element<0, T>::type const& x() const {
    return get<0>(*this);
  }
  template <typename T = tuple<As...> >
  typename tuple_element<0, T>::type& x() {
    return get<0>(*this);
  }
  template <typename T = tuple<As...> >
  typename tuple_element<1, T>::type const& y() const {
    return get<1>(*this);
  }
  template <typename T = tuple<As...> >
  typename tuple_element<1, T>::type& y() {
    return get<1>(*this);
  }
  template <typename T = tuple<As...> >
  typename tuple_element<2, T>::type const& z() const {
    return get<2>(*this);
  }
  template <typename T = tuple<As...> >
  typename tuple_element<2, T>::type& z() {
    return get<2>(*this);
  }
  template <typename T = tuple<As...> >
  typename tuple_element<3, T>::type const& w() const {
    return get<3>(*this);
  }
  template <typename T = tuple<As...> >
  typename tuple_element<3, T>::type& w() {
    return get<3>(*this);
  }
};
using lli = long long int;
using llu = long long unsigned;
using pii = tpl<lli, lli>;
using piii = tpl<lli, lli, lli>;
using piiii = tpl<lli, lli, lli, lli>;
using vi = vector<lli>;
using vii = vector<pii>;
using viii = vector<piii>;
using vvi = vector<vi>;
using vvii = vector<vii>;
using vviii = vector<viii>;
template <class T>
using min_queue = priority_queue<T, vector<T>, greater<T> >;
template <class T>
using max_queue = priority_queue<T>;
template <size_t... I>
struct my_index_sequence {
  using type = my_index_sequence;
  static constexpr array<size_t, sizeof...(I)> value = {{I...}};
};
namespace my_index_sequence_detail {
template <typename I, typename J>
struct concat;
template <size_t... I, size_t... J>
struct concat<my_index_sequence<I...>, my_index_sequence<J...> >
    : my_index_sequence<I..., (sizeof...(I) + J)...> {};
template <size_t N>
struct make_index_sequence
    : concat<typename make_index_sequence<N / 2>::type,
             typename make_index_sequence<N - N / 2>::type>::type {};
template <>
struct make_index_sequence<0> : my_index_sequence<> {};
template <>
struct make_index_sequence<1> : my_index_sequence<0> {};
}  // namespace my_index_sequence_detail
template <class... A>
using my_index_sequence_for =
    typename my_index_sequence_detail::make_index_sequence<sizeof...(A)>::type;
template <class T, size_t... I>
void print_tuple(ostream& s, T const& a, my_index_sequence<I...>) {
  using swallow = int[];
  (void)swallow{0, (void(s << (I == 0 ? "" : ", ") << get<I>(a)), 0)...};
}
template <class T>
ostream& print_collection(ostream& s, T const& a);
template <class... A>
ostream& operator<<(ostream& s, tpl<A...> const& a);
template <class... A>
ostream& operator<<(ostream& s, tuple<A...> const& a);
template <class A, class B>
ostream& operator<<(ostream& s, pair<A, B> const& a);
template <class T, size_t I>
ostream& operator<<(ostream& s, array<T, I> const& a) {
  return print_collection(s, a);
}
template <class T>
ostream& operator<<(ostream& s, vector<T> const& a) {
  return print_collection(s, a);
}
template <class T, class U>
ostream& operator<<(ostream& s, multimap<T, U> const& a) {
  return print_collection(s, a);
}
template <class T>
ostream& operator<<(ostream& s, multiset<T> const& a) {
  return print_collection(s, a);
}
template <class T, class U>
ostream& operator<<(ostream& s, map<T, U> const& a) {
  return print_collection(s, a);
}
template <class T>
ostream& operator<<(ostream& s, set<T> const& a) {
  return print_collection(s, a);
}
template <class T>
ostream& print_collection(ostream& s, T const& a) {
  s << '[';
  for (auto it = begin(a); it != end(a); ++it) {
    s << *it;
    if (it != prev(end(a))) s << " ";
  }
  return s << ']';
}
template <class... A>
ostream& operator<<(ostream& s, tpl<A...> const& a) {
  s << '(';
  print_tuple(s, a, my_index_sequence_for<A...>{});
  return s << ')';
}
template <class... A>
ostream& operator<<(ostream& s, tuple<A...> const& a) {
  s << '(';
  print_tuple(s, a, my_index_sequence_for<A...>{});
  return s << ')';
}
template <class A, class B>
ostream& operator<<(ostream& s, pair<A, B> const& a) {
  return s << "(" << get<0>(a) << ", " << get<1>(a) << ")";
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  lli n, m;
  cin >> n >> m;
  vi C(n);
  for (lli i = 0; i < (lli)(n); ++i) cin >> C[i];
  vi W(m, 0);
  vvii G(n);
  for (lli i = 0; i < (lli)(m); ++i) {
    int u, v;
    cin >> u >> v;
    --u;
    --v;
    G[u].push_back(make_tuple(v, i));
    G[v].push_back(make_tuple(u, i));
  }
  vi E(n);
  vi depth(n);
  function<lli(int, lli)> dfs = [&](int i, lli d) {
    depth[i] = d;
    E[i] = 1;
    lli c = C[i];
    for (auto e_ : G[i]) {
      int j, e;
      tie(j, e) = e_;
      if (!E[j]) {
        lli cj = dfs(j, d + 1);
        c -= cj;
      }
    }
    return c;
  };
  lli r = dfs(0, 0);
  if (r & 1) {
    cout << "NO" << endl;
    return 0;
  }
  for (lli i = 0; i < (lli)(n); ++i)
    for (auto e_ : G[i]) {
      int j, e;
      tie(j, e) = e_;
      if (depth[i] % 2 == depth[j] % 2) {
        W[e] = (depth[i] & 1) ? -r / 2 : r / 2;
        r = 0;
        C[i] -= W[e];
        C[j] -= W[e];
        goto l1;
      }
    }
l1:;
  if (r) {
    cout << "NO" << endl;
    return 0;
  }
  E.assign(n, 0);
  function<void(int)> dfs2 = [&](int i) {
    E[i] = 1;
    for (auto e_ : G[i]) {
      int j, e;
      tie(j, e) = e_;
      if (!E[j]) {
        dfs2(j);
        W[e] = C[j];
        C[j] -= W[e];
        C[i] -= W[e];
      }
    }
  };
  dfs2(0);
  cout << "YES" << endl;
  for (lli i = 0; i < (lli)(m); ++i) {
    cout << W[i] << '\n';
  }
  return 0;
}