分数: 333 分
问题陈述
高桥被任命负责组织学校的舞会。有 N 参与者,每个编号为 1 to N.
在舞会上,参与者结伴跳舞。然而,这所学校有一个独特的传统:每个参与者 i 有一个称为“优先级”的正整数值 R_i。优先级较高(价值较大)的人有权优先选择自己的伴侣。
Aoki 是参与者编号 1,他关心他的搭档是谁。
M 已从参与者中提前指定“配对候选人”。的 j-th 对候选者是一对参与者 U_j 和参与者 V_j,表示参与者 U_j 和参与者 V_j 是要相互配对的候选者。只能由这些组成对 M 候选人。
配对规则如下:
- 全部设置 N 参与者的合作伙伴尚未确定。
- 在未确定搭档的参赛者中,选择优先级最高的一名参赛者 R_i。致电该参与者 x.
- 与参赛者配对候选人的参赛者中 x 且其搭档未定,选择参赛人数最少的一位。致电该参与者 y。配对参与者 x 与参与者 y.
- 重复步骤 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