#include <bits/stdc++.h>
int main() {
  using namespace std;
  unsigned long N, M;
  cin >> N >> M;
  vector<unsigned long> D(N);
  for (auto& i : D) cin >> i;
  vector<unsigned long> edges(M);
  vector<vector<unsigned long>> edge(N);
  for (unsigned long i{0}, u, v; i < M; ++i) {
    cin >> u >> v;
    edge[--u].push_back(i);
    edge[--v].push_back(i);
    edges[i] = u ^ v;
  }
  vector<unsigned long> ans(M, 1000000000);
  vector<unsigned long> uf(2 * N), sz(2 * N, 1);
  iota(uf.begin(), uf.end(), 0UL);
  const auto& find = [&uf](unsigned long i) -> unsigned long {
    while (i != uf[i]) i = uf[i] = uf[uf[i]];
    return i;
  };
  const auto& unite = [&uf, &sz, &find](unsigned long i,
                                        unsigned long j) -> void {
    i = find(i);
    j = find(j);
    if (i == j) return;
    if (sz[i] < sz[j]) swap(i, j);
    sz[i] += sz[j];
    uf[j] = i;
  };
  const auto& con = [&uf, &find](unsigned long i, unsigned long j) -> bool {
    return find(i) == find(j);
  };
  [&] {
    for (unsigned long i{0}; i < N; ++i)
      if ([&] {
            for (auto j : edge[i])
              if (D[i] >= D[edges[j] ^ i]) {
                ans[j] = D[i];
                unite(i, (edges[j] ^ i) + N);
                unite(i + N, edges[j] ^ i);
                return false;
              }
            return true;
          }()) {
        puts("-1");
        exit(0);
      }
  }();
  for (unsigned long i{0}; i < N; ++i) putchar(66 + 21 * con(0, i));
  cout << endl;
  for (const auto& i : ans) cout << i << endl;
  return 0;
}
