B - Pairing for the Dance Party Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 333 点

問題文

高橋君は学校のダンスパーティーの運営を任されました。参加者は N 人おり、それぞれ 1 から N までの番号が付けられています。

ダンスパーティーでは、参加者同士がペアを組んで踊ります。ただし、この学校には独特な伝統があり、各参加者 i には「優先度」と呼ばれる正の整数値 R_i が定められています。優先度が高い（値が大きい）人ほど先にペア相手を選ぶ権利があります。

青木君は参加者番号 1 の人物であり、自分がどの相手とペアになるかを気にしています。

参加者の中から M 組の「ペア候補」が事前に指定されています。 j 番目のペア候補は参加者 U_j と参加者 V_j の組であり、これは参加者 U_j と参加者 V_j が互いにペアを組む相手の候補であることを意味します。ペアは、この M 組の候補の中からのみ組むことができます。

ペア決めのルールは以下の通りです：

  1. N 人全員のペア相手を未定とする。
  2. ペア相手が未定の参加者のうち、優先度 R_i が最も大きい参加者を 1 人選ぶ。この人を参加者 x とする。
  3. 参加者 x とペア候補の関係にあり、かつペア相手が未定である参加者のうち、参加者番号が最も小さい人を 1 人選ぶ。この人を参加者 y とする。参加者 x と参加者 y をペアにする。
  4. ペア相手が未定の参加者がいなくなるまで、手順 2〜3 を繰り返す。

このルールにより、全体で N / 2 組のペアが作られます（ N は偶数であることが保証されます）。

優先度の値 R_i は全員異なるため、手順 2 で選ばれる参加者は一意に定まります。また、手順 3 で参加者 x がペア候補の中から選べる相手が 0 人になることはないことが保証されます（すなわち、すべての参加者がちょうど 1 人の相手とペアを組めるような入力のみが与えられます）。

このルールに従ってペアの組み合わせを決めたとき、青木君（参加者番号 1 ）のペア相手の参加者番号を求めてください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • N は偶数
  • \frac{N}{2} \leq M \leq \min\left(\frac{N(N-1)}{2},\ 2 \times 10^5\right)
  • 1 \leq R_i \leq 10^9 （1 \leq i \leq N）
  • R_i はすべて異なる
  • 1 \leq U_j < V_j \leq N （1 \leq j \leq M）
  • (U_j, V_j) はすべて異なる
  • すべての参加者がちょうど 1 人の相手とペアを組めることが保証される
  • 入力はすべて整数

入力

N M
R_1 R_2 \ldots R_N
U_1 V_1
U_2 V_2
:
U_M V_M
  • 1 行目には、参加者の人数を表す N と、ペア候補の数を表す M が、スペース区切りで与えられる。
  • 2 行目には、各参加者の優先度を表す R_1, R_2, \ldots, R_N がスペース区切りで与えられる。
  • 続く M 行にわたって、ペア候補の情報が与えられる。
  • そのうち j 行目（入力全体では 2 + j 行目）では、 j 番目のペア候補である参加者 U_j と参加者 V_j が、スペース区切りで与えられる。

出力

青木君（参加者番号 1 ）のペア相手の参加者番号を 1 行で出力せよ。

入力例 1

4 3
10 20 30 40
1 2
1 3
3 4

出力例 1

2

入力例 2

6 4
100 50 80 70 60 90
1 2
1 3
3 4
5 6

出力例 2

2

入力例 3

10 7
50 15 25 35 45 55 65 75 85 95
1 2
1 4
2 3
3 4
5 6
7 8
9 10

出力例 3

2

入力例 4

20 12
50 40 100 90 80 70 60 55 45 35 30 25 20 15 10 5 95 85 75 65
1 2
1 3
2 4
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20

出力例 4

3

入力例 5

2 1
1 2
1 2

出力例 5

2

Score : 333 pts

Problem Statement

Takahashi has been put in charge of organizing the school's dance party. There are N participants, each numbered from 1 to N.

At the dance party, participants form pairs to dance together. However, this school has a unique tradition: each participant i has a positive integer value called "priority" R_i. A person with higher priority (larger value) has the right to choose their partner first.

Aoki is participant number 1, and he is concerned about who his partner will be.

M "pair candidates" have been designated in advance from among the participants. The j-th pair candidate is the pair of participant U_j and participant V_j, meaning that participant U_j and participant V_j are candidates to be paired with each other. Pairs can only be formed from these M candidates.

The pairing rules are as follows:

  1. Set all N participants' partners as undetermined.
  2. Among the participants whose partner is undetermined, select the one participant with the highest priority R_i. Call this participant x.
  3. Among the participants who are pair candidates with participant x and whose partner is undetermined, select the one with the smallest participant number. Call this participant y. Pair participant x with participant y.
  4. Repeat steps 2–3 until there are no participants with undetermined partners.

By this rule, a total of N / 2 pairs are formed (N is guaranteed to be even).

Since all priority values R_i are distinct, the participant selected in step 2 is uniquely determined. It is also guaranteed that in step 3, participant x will never have 0 available candidates to choose from (that is, the input is guaranteed to allow every participant to be paired with exactly one partner).

Determine the participant number of Aoki's (participant number 1) partner when the pairs are decided according to this rule.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • N is even
  • \frac{N}{2} \leq M \leq \min\left(\frac{N(N-1)}{2},\ 2 \times 10^5\right)
  • 1 \leq R_i \leq 10^9 (1 \leq i \leq N)
  • All R_i are distinct
  • 1 \leq U_j < V_j \leq N (1 \leq j \leq M)
  • All (U_j, V_j) are distinct
  • It is guaranteed that every participant can be paired with exactly one partner
  • All input values are integers

Input

N M
R_1 R_2 \ldots R_N
U_1 V_1
U_2 V_2
:
U_M V_M
  • The first line contains N, the number of participants, and M, the number of pair candidates, separated by a space.
  • The second line contains the priorities R_1, R_2, \ldots, R_N of each participant, separated by spaces.
  • The following M lines contain the pair candidate information.
  • The j-th of these lines (the (2 + j)-th line overall) contains participant U_j and participant V_j of the j-th pair candidate, separated by a space.

Output

Output the participant number of Aoki's (participant number 1) partner on a single line.

Sample Input 1

4 3
10 20 30 40
1 2
1 3
3 4

Sample Output 1

2

Sample Input 2

6 4
100 50 80 70 60 90
1 2
1 3
3 4
5 6

Sample Output 2

2

Sample Input 3

10 7
50 15 25 35 45 55 65 75 85 95
1 2
1 4
2 3
3 4
5 6
7 8
9 10

Sample Output 3

2

Sample Input 4

20 12
50 40 100 90 80 70 60 55 45 35 30 25 20 15 10 5 95 85 75 65
1 2
1 3
2 4
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20

Sample Output 4

3

Sample Input 5

2 1
1 2
1 2

Sample Output 5

2