← 返回题目列表

AtCoder · awc0043_b

B. 舞会配对

中文机器翻译题面 查看原题

分数: 333 分

问题陈述

高桥被任命负责组织学校的舞会。有 N 参与者,每个编号为 1 to N.

在舞会上,参与者结伴跳舞。然而,这所学校有一个独特的传统:每个参与者 i 有一个称为“优先级”的正整数值 R_i。优先级较高(价值较大)的人有权优先选择自己的伴侣。

Aoki 是参与者编号 1,他关心他的搭档是谁。

M 已从参与者中提前指定“配对候选人”。的 j-th 对候选者是一对参与者 U_j 和参与者 V_j,表示参与者 U_j 和参与者 V_j 是要相互配对的候选者。只能由这些组成对 M 候选人。

配对规则如下:

  1. 全部设置 N 参与者的合作伙伴尚未确定。
  2. 在未确定搭档的参赛者中,选择优先级最高的一名参赛者 R_i。致电该参与者 x.
  3. 与参赛者配对候选人的参赛者中 x 且其搭档未定,选择参赛人数最少的一位。致电该参与者 y。配对参与者 x 与参与者 y.
  4. 重复步骤 2-3,直到没有任何参与者具有未确定的合作伙伴。

根据此规则,总共 N / 2 对形成 (N 保证是偶数)。

由于所有优先级值 R_i 是不同的,步骤 2 中选择的参与者是唯一确定的。还保证在步骤 3 中,参与者 x 永远不会有 0 可供选择的候选者(也就是说,输入保证允许每个参与者与恰好一个伙伴配对)。

确定青木的参与者编号(参与者编号 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) 是不同的
  • 保证每位参赛者只能与一位伙伴配对
  • 所有输入值均为整数

输入

N M
R_1 R_2 \ldots R_N
U_1 V_1
U_2 V_2
:
U_M V_M
  • 第一行包含 N,参与者数量,以及 M,候选对的数量,以空格分隔。
  • 第二行包含优先级 每个参与者的 R_1, R_2, \ldots, R_N ,用空格分隔。
  • 以下 M 行包含配对候选信息。
  • 的 j- 这些行( (2 + j)- 总体第行)包含参与者 U_j 和参与者 V_j 的 j- 第对候选者,以空格分隔。

输出

输出青木的参加人数(参加人数 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