(ユーザー解説です)

簡単のため \(M = 0\) の場合で説明します。(\(M \neq 0\) の場合は、公式解説と同様の処理を適宜行ってください。)

列 \(p_i\) を、\(p_i :=\) (連結成分のうち辺を貼るべき頂点を重複度込みで並べた列) として定義します。
わかりづらいので具体例で説明すると、たとえば \(N = 5, D = \lbrace3,2,1,1,1\rbrace\) の場合、はじめの時点では

\[p[1] = \lbrace1, 1, 1\rbrace, p[2] = \lbrace2, 2\rbrace\]

\[p[3] = \lbrace3\rbrace, p[4] = \lbrace4\rbrace, p[5] = \lbrace5\rbrace\]

となります。

次に、列同士をマージしていきながら辺を貼っていきます。 これは、残っている列が \(2\) 本以上ある間、以下の操作を繰り返し行えばよいです。

• 列を長さの大きい方から 2 つ選ぶ。
• それぞれの末尾の要素を 1 個ずつ pop して、pop した頂点間に辺を貼る。
• 短い方を長い方に連結させる。

たとえば上の例からマージを一回行うと、\(p[1]\) と \(p[2]\) をマージして

\[p[1] = \lbrace1, 1, 2\rbrace\]

\[p[3] = \lbrace3\rbrace, p[4] = \lbrace4\rbrace, p[5] = \lbrace5\rbrace\]

\[(答え) = \lbrace(1, 2)\rbrace\]

になり、もう \(1\) 回マージを行うと \(p[1]\) と \(p[3]\) をマージして

\[p[1] = \lbrace1, 1\rbrace\]

\[ p[4] = \lbrace4\rbrace, p[5] = \lbrace5\rbrace\]

\[(答え) = \lbrace(1, 2), (2, 3)\rbrace\]

になります。

すべての列をマージする操作は、 std::priority_queue とマージテクを利用すれば全体で \(O(N \log N)\) で行うことができます。 問題文の条件を満たすように辺を貼ることが可能かどうかは、最終的に追加する辺が \(N-M-1\) 本になっているかどうかで判定すればよいです。

実装例 (C++)

#include <algorithm>
#include <iostream>
#include <numeric>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
#include "atcoder/dsu.hpp"

void No() {
  cout << "-1\n";
  exit(0);
}

#define rep(i, n) for (int i = 0; i < (n); i++)

int main() {
  int N, M;
  cin >> N >> M;
  vector<long long> D(N);
  for (auto& x : D) cin >> x;
  if (accumulate(begin(D), end(D), 0LL) != 2 * N - 2) No();
  atcoder::dsu dsu(N);
  for (int i = 0, a, b; i < M; i++) {
    cin >> a >> b;
    --a, --b;
    D[a]--, D[b]--;
    if (dsu.same(a, b)) No();
    dsu.merge(a, b);
  }
  vector<vector<int>> ps(N);
  rep(i, N) {
    if (D[i] < 0) No();
    rep(_, D[i]) ps[dsu.leader(i)].push_back(i);
  }

  priority_queue<pair<int, int>> Q;
  rep(i, N) if (ps[i].size()) Q.emplace(ps[i].size(), i);
  vector<pair<int, int>> ans;
  while ((int)Q.size() >= 2) {
    auto [si, i] = Q.top();
    Q.pop();
    auto [sj, j] = Q.top();
    Q.pop();
    ans.emplace_back(ps[i].back(), ps[j].back());
    ps[i].pop_back(), ps[j].pop_back();
    if (si < sj) swap(ps[i], ps[j]);
    copy(begin(ps[j]), end(ps[j]), back_inserter(ps[i]));
    if (si + sj - 2 > 0) Q.emplace(si + sj - 2, i);
  }

  if ((int)ans.size() != N - M - 1) No();
  for (auto& [u, v] : ans) cout << u + 1 << " " << v + 1 << "\n";
}