この問題は、問題文中の操作を適切にシミュレーションすることで解くことができます。

より詳細には、次のようなアルゴリズムを実装することで解くことができます。

1. はじめ、それぞれの参加者のペア相手が決まっているかどうかを表す列 \(\text{used}\) を \((\text{false},\text{false},\ldots,\text{false})\) で初期化する。
2. 次に、参加者番号を優先度が高い順に並べて \(P _ 1,P _ 2,\ldots,P _ N\) とする。
3. \(i=1,2,\ldots,N\) の順に以下を繰り返す。
   1. 参加者 \(P _ i\) のペア相手が決まっているなら（\(\text{used} _ {P _ i}=\text{true}\) なら）、処理を打ち切って次の \(i\) に進む。
   2. 参加者 \(P _ i\) のペア候補をすべて確認し、ペア相手が未定である中で参加者番号が最小の相手 \(Q _ i\) を求める。
   3. \(P _ i\) の相手を \(Q _ i\) に、\(Q _ i\) の相手を \(P _ i\) とし、\(\text{used} _ {P _ i},\text{used} _ {Q _ i}\) を \(\text{true}\) に更新する。
4. 参加者 \(1\) の相手を出力する。

ペア候補を入力から読み込む際に、「参加者 \(i\) のペア候補の一覧」をすべての \(i\) に対して作成しておく（グラフの隣接リストと同様の形式）ことで、上の 3-2. の繰り返しを合計で \(2M\) 回とすることができます。 時間計算量は \(O(N+M)\) などとなります。

定数倍高速化として、

• \(i\) のペア候補のリストには参加者 \(i\) より優先度が低い参加者しか追加しなくてよい
  • 参加者 \(i\) のペア候補のリストを確認する時点では、より優先度が高い参加者のペア相手は確定しているため
• 参加者 \(1\) の相手が確定した時点で処理を打ち切ってよい

などがありますが、最悪時間計算量のオーダーは変化しません。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> R(N);
    for (int& r : R)
        cin >> r;
    vector<vector<int>> pair_candidate(N); // i 番目の参加者のペア候補の一覧
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        --u;
        --v; // 0-indexed にしておく
        pair_candidate[u].emplace_back(v);
        pair_candidate[v].emplace_back(u);
    }

    vector<int> precedence_index(N);
    iota(begin(precedence_index), end(precedence_index), 0U);
    ranges::sort(precedence_index, greater{}, [&R](int i){return R[i];}); // R が大きいほうから並べる

    vector<int> ans(N); // i 番目の相手
    vector<bool> used(N); // i 番目の相手が決まっているか
    for (int i : precedence_index) { // 優先度が高いほうからみて
        if (!used[i]) { // ペア相手が未定なら
            int pair_index = N;
            for (int j : pair_candidate[i]) { // ペア候補のうち
                if (!used[j]) { // ペア相手が未定の中で
                    pair_index = min(j, pair_index); // 一番数字が小さい人を求める
                }
            }

            used[i] = used[pair_index] = true;
            ans[i] = pair_index;
            ans[pair_index] = i;
        }
    }
    
    cout << ans[0] + 1 << endl; // 1-indexed に直して出力
    return 0;
}

N, M = map(int, input().split())

R = list(map(int, input().split()))

pair_candidate = [[] for _ in range(N)] # i 番目の参加者のペア候補の一覧
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1 # 0-indexed にしておく
    pair_candidate[u].append(v)
    pair_candidate[v].append(u)

precedence_index = sorted(range(N), reverse=True, key=lambda x: R[x]) # R が大きいほうから並べる

ans = [0 for _ in range(N)] # i 番目の相手
used = [False for _ in range(N)] # i 番目の相手が決まっているか
for i in precedence_index: # 優先度が高いほうからみて
    if not used[i]: # ペア相手が未定なら
        pair_index = N
        for j in pair_candidate[i]: # ペア候補のうち
            if not used[j]: # ペア相手が未定の中で
                pair_index = min(j, pair_index) # 一番数字が小さい人を求める

        used[i] = True
        used[pair_index] = True
        ans[i] = pair_index
        ans[pair_index] = i

print(ans[0] + 1) # 1-indexed に直して出力