Overview

We simulate the operation of forming pairs in order from the person with the highest priority, where each person selects “the opponent with the smallest participant number among the still-undecided candidates,” and we only need to find the opponent of participant 1 (Aoki).

Analysis

This pair-deciding process simply repeats:

• Step 2: Select the person \(x\) with the highest priority among the undecided
  
• Step 3: Among \(x\)’s candidates, select the person \(y\) who is “undecided” and has the “smallest participant number”

The two key observations here are:

1. The priorities \(R_i\) are all distinct
   Therefore, the order of selection in step 2 is uniquely determined from the start, and there is no need to “find the maximum” each time.
   → We can sort the participants in descending order of \(R\) beforehand and process them in that order.

2. Step 3 is the problem of “finding the undecided adjacent vertex with the smallest number”
   If we sort each participant \(x\)’s candidate list (adjacency list) in ascending order of participant number, we can scan from the beginning and the first “still undecided” person we find is the minimum.

A naive approach would, for example, each time: - Search for the maximum \(R\) among the undecided (\(O(N)\)) - Search for the undecided candidate with the smallest number (worst case \(O(\text{degree})\))

Repeating this \(N/2\) times leads to worst-case \(O(N^2)\) scale, which is too slow.

Instead, by: - Sorting participants by priority only once - Sorting each adjacency list by number only once - Then processing in order

we can efficiently simulate the process.

Also, since we only need to find “the opponent of participant 1,” we can output and terminate the moment participant 1 is paired.

Algorithm

1. Think of it as a graph (participants = vertices, pair candidates = undirected edges).
2. Build the adjacency list adj[i] for each vertex \(i\), and sort it in ascending order of participant number.
3. Create an array order with participants sorted in descending order of priority \(R_i\) (this is the selection order for step 2).
4. Prepare matched[i] (whether participant \(i\) has already been paired), and process in the order of order:
   • If matched[x] = True, skip.
   • Scan adj[x] in ascending order and find the first \(y\) satisfying matched[y] = False (this is the “smallest number” from step 3).
   • Set matched[x] = matched[y] = True to finalize the pair.
   • If \(x = 1\) or \(y = 1\), output the opponent and terminate.

The correctness of this method follows from: - order reproduces “the person with the highest priority among the undecided” by processing from front to back - Scanning adj[x] in ascending order and taking the first undecided opponent found is exactly “the undecided candidate with the smallest participant number”

Furthermore, “an opponent is always found” is guaranteed by the problem statement.

Complexity

• Time complexity:
  
  • Sorting adjacency lists: \(\sum_i O(\deg(i)\log \deg(i)) \le O(M\log M)\)
    
  • Sorting by priority: \(O(N\log N)\)
    
  • Scanning (each vertex is paired at most once, and the adjacency list is scanned from the front only as needed): total \(O(M)\)
    Overall: \(O(N\log N + M\log M)\)
• Space complexity: \(O(N+M)\) (graph and management arrays)

Implementation Notes

• Fast input: Since \(N, M \le 2\times 10^5\), using sys.stdin.buffer.read() for bulk reading provides stability.

• Adjacency lists must be sorted in ascending order: This directly realizes the “smallest number” requirement of step 3.

• Undecided check via matched: Even if the first candidate in the list is already paired, advancing to the next will always (by guarantee) find an unpaired opponent.

• Terminate immediately when participant 1 is paired: There is no need to simulate until the end.

  Source Code

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()

---

This editorial was generated by gpt-5.2-high.