概要

優先度が高い人から順に「まだ未決定の候補の中で参加者番号が最小の相手」を選んでペアを作る操作をそのまま再現し、参加者 1（青木君）の相手だけを求めます。

考察

このペア決めは、

• 手順 2：未決定の中で優先度最大の人 \(x\) を選ぶ
  
• 手順 3：\(x\) の候補のうち「未決定」かつ「参加者番号最小」の人 \(y\) を選ぶ

を繰り返すだけです。

ここで重要な観察は次の 2 点です。

1. 優先度 \(R_i\) は全員異なる
   したがって、手順 2 で選ばれる順番は最初から一意に定まり、毎回「最大値を探す」必要はありません。
   → あらかじめ参加者を \(R\) の降順にソートして、その順に処理すればよいです。

2. 手順 3 は「最小番号の未決定の隣接頂点」を探す問題
   各参加者 \(x\) について候補（隣接リスト）を参加者番号で昇順にソートしておけば、先頭から見ていって「まだ未決定の人」を最初に見つけた時点でそれが最小です。

素朴にやると、例えば毎回 - 未決定の中から最大 \(R\) を探す（\(O(N)\)） - 候補から最小番号の未決定を探す（最悪 \(O(\text{次数})\)）

となり、これを \(N/2\) 回繰り返すので最悪 \(O(N^2)\) 規模になって間に合いません。

そこで、 - 参加者を優先度で一度だけソート - 各隣接リストを番号順に一度だけソート - あとは順番に見ていく

ことで高速にシミュレーションできます。

また、求めたいのは「参加者 1 の相手」だけなので、1 がペアになった瞬間に出力して終了できます。

アルゴリズム

1. グラフとして考える（参加者＝頂点、ペア候補＝無向辺）。
2. 各頂点 \(i\) の隣接リスト adj[i] を作り、参加者番号で昇順ソートする。
3. 参加者を優先度 \(R_i\) の降順に並べた配列 order を作る（これが手順 2 の選択順）。
4. matched[i]（参加者 \(i\) がすでにペア確定しているか）を用意し、order の順に次を行う：
   • すでに matched[x] = True ならスキップ。
   • adj[x] を小さい順に見ていき、matched[y] = False を満たす最初の \(y\) を見つける（これが手順 3 の「最小番号」）。
   • matched[x] = matched[y] = True としてペア確定。
   • \(x=1\) または \(y=1\) なら、相手を出力して終了。

この方法が正しい理由は、 - order が常に「未決定の中で優先度最大」を前から順に再現していること - adj[x] を小さい順に走査して最初に見つかる未決定の相手が、まさに「未決定の中で参加者番号最小」であること
によります。さらに「必ず相手が見つかる」ことは問題文で保証されています。

計算量

• 時間計算量:
  
  • 隣接リストのソート：\(\sum_i O(\deg(i)\log \deg(i)) \le O(M\log M)\)
    
  • 優先度順ソート：\(O(N\log N)\)
    
  • 走査（各頂点は高々1回ペアを組み、隣接リストもそのときに必要な分だけ前から見る）：合計 \(O(M)\)
    よって全体で \(O(N\log N + M\log M)\)
• 空間計算量: \(O(N+M)\)（グラフと管理配列）

実装のポイント

• 高速入力：\(N,M \le 2\times 10^5\) なので sys.stdin.buffer.read() で一括読み込みにすると安定します。

• 隣接リストは必ず昇順ソート：手順 3 の「番号最小」をそのまま実現できます。

• matched による未決定判定：候補の先頭がすでに確定済みでも、次へ進めば必ず（保証により）未確定の相手が見つかります。

• 参加者 1 がペアになったら即終了：最後までシミュレーションする必要がありません。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)
    R = [0] * (N + 1)
    for i in range(1, N + 1):
        R[i] = next(it)

    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = next(it)
        v = next(it)
        adj[u].append(v)
        adj[v].append(u)

    for i in range(1, N + 1):
        adj[i].sort()

    order = list(range(1, N + 1))
    order.sort(key=lambda i: R[i], reverse=True)

    matched = [False] * (N + 1)
    idx = [0] * (N + 1)

    for x in order:
        if matched[x]:
            continue
        lst = adj[x]
        i = idx[x]
        while True:
            y = lst[i]
            i += 1
            if not matched[y]:
                break
        matched[x] = matched[y] = True
        if x == 1:
            sys.stdout.write(str(y))
            return
        if y == 1:
            sys.stdout.write(str(x))
            return

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。