Overview

This is a problem where you simulate the process of pairing participants in order of decreasing priority, where each participant selects the unpaired partner with the smallest number from their list of pair candidates, and you need to find the pair partner of participant 1 (Aoki).

Analysis

Essence of the Problem

This problem requires simulating a pairing process based on clear rules (greedy algorithm).

1. Process participants in order of decreasing priority: First, sort all participants in descending order of priority \(R_i\), and process them in that order.
2. Each participant selects the unpaired partner with the smallest number from their candidates: When it is participant \(x\)’s turn, they select the person with the smallest number among the still-unpaired participants in \(x\)’s adjacency list (pair candidates).

Issues with the Naive Approach

If we naively scan through each participant’s entire adjacency list every time, in the worst case we would repeatedly traverse the total adjacency list length \(O(M)\), leading to an overall time complexity close to \(O(N \times M)\).

Solution

By managing adjacency lists with a sorted data structure (SortedList), we can iterate in order of increasing number, and the first unpaired candidate found is immediately the answer. Furthermore, by terminating the process immediately when participant 1 gets paired, we avoid unnecessary computation.

In practice, each participant becomes the initiator of a pairing at most once, and each edge is referenced only a constant number of times, so the total traversal is not that large.

Algorithm

1. Read input: Read the number of participants \(N\), the number of pair candidates \(M\), each participant’s priority \(R_i\), and pair candidates \((U_j, V_j)\).
2. Build adjacency lists: For each participant, manage their pair candidates using a SortedList (a list that is always kept sorted).
3. Sort participants in descending order of priority: Create an array order containing participant numbers arranged in descending order of priority \(R_i\).
4. Simulation:
   • Take participant \(x\) from the front of order.
   • If \(x\) is already paired, skip.
   • Scan \(x\)’s adjacency list (SortedList) from the smallest number, and pair \(x\) with the first unpaired participant \(y\) found.
   • If \(x\) or \(y\) is participant 1, record the partner’s number and terminate.
5. Output the result.

Concrete Example

For \(N=4, M=3\), \(R = [3, 10, 1, 5]\) (participants 1–4), with candidates \((1,2), (1,3), (3,4)\):

• Descending priority order: Participant 2 (\(R=10\)) → Participant 4 (\(R=5\)) → Participant 1 (\(R=3\)) → Participant 3 (\(R=1\))
• Participant 2’s candidates: \(\{1\}\) → Pairs with participant 1
• The answer is 2 (participant 1’s partner is participant 2)

Complexity

• Time complexity: \(O(N \log N + M \log N)\)
  • Sorting participants: \(O(N \log N)\)
  • Insertions into adjacency lists (SortedList): \(O(M \log N)\) in total
  • The simulation part references each edge at most a constant number of times: \(O(M)\) (with possible early termination once participant 1’s pair is determined)
• Space complexity: \(O(N + M)\) (adjacency lists and sorting arrays)

Implementation Notes

• Using SortedList: By using Python’s sortedcontainers.SortedList, adjacency lists are always kept sorted, allowing efficient lookup of the unpaired candidate with the smallest number.

• Early termination: By breaking out of the loop immediately when Aoki (participant 1) gets paired, unnecessary computation is avoided.

• paired array: A flag array is prepared to determine in \(O(1)\) whether each participant is already paired.

  Source Code

import sys
from sortedcontainers import SortedList

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    R = [0] * (N + 1)
    for i in range(1, N + 1):
        R[i] = int(input_data[idx]); idx += 1
    
    # adjacency list using SortedList for each node
    adj = [None] * (N + 1)
    for i in range(1, N + 1):
        adj[i] = SortedList()
    
    for j in range(M):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        adj[u].add(v)
        adj[v].add(u)
    
    # Sort participants by priority descending
    # We need to process in order of decreasing R[i]
    order = sorted(range(1, N + 1), key=lambda i: -R[i])
    
    paired = [False] * (N + 1)
    answer = -1
    
    # To efficiently get the next unpaired person with highest priority,
    # we just iterate through the sorted order and skip paired ones
    for x in order:
        if paired[x]:
            continue
        # Find the smallest-numbered unpaired candidate in adj[x]
        # adj[x] is a SortedList, so we iterate from smallest
        y = None
        for candidate in adj[x]:
            if not paired[candidate]:
                y = candidate
                break
        
        # Pair x and y
        paired[x] = True
        paired[y] = True
        
        if x == 1:
            answer = y
            break
        if y == 1:
            answer = x
            break
    
    print(answer)

if __name__ == '__main__':
    main()

---

This editorial was generated by claude4.6opus-thinking.