分数: 400 分
问题陈述
高桥是某个地区的测量员。该区域包含 N 城市,编号自 1 to N。各城市之间由单向道路连接,并且有 M 道路总数。道路 j 是一条从城市出发的单向道路 U_j 前往城市 V_j,允许从城市直接出行 U_j 前往城市 V_j (无法反向行驶)。
每个城市都有一个独特的重要性值。城市的重要性 i is B_i. B_1, B_2, \ldots, B_N 是以下整数的排列 1 to N.
Takahashi 通过重复以下过程对所有城市进行调查。最初,所有城市都没有进行调查。
- 确定起始城市。 首次游览,起始城市为 city 1。对于后续的每次游览,起始城市是重要性最高的未调查城市。
- 从出发城市进行游览。 首先,标记调查的起始城市。然后,重复以下操作:
- 如果从当前城市单条道路直达的城市中至少存在一个未调查的城市,则移动到具有该城市的城市 最高重要性 其中 ,并将该城市标记为调查对象。
- 如果当前城市单条道路可直达的城市中不存在未调查的城市(包括根本不存在可达城市的情况), 结束本次游览.
- 如果所有城市都已被调查,则停止。否则,返回步骤 1。
按从第一个到最后一个的顺序输出 Takahashi 将城市标记为调查的序列。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- 1 \leq B_i \leq N
- B_1, B_2, \ldots, B_N 都是不同的
- 1 \leq U_j \leq N
- 1 \leq V_j \leq N
- U_j \neq V_j
- 同一对 (U_j, V_j) 未给出多次
- 所有输入值均为整数
输入
N M B_1 B_2 \ldots B_N U_1 V_1 U_2 V_2 \vdots U_M V_M
- 第一行包含 N,城市数量,以及 M,道路数量,以空格分隔。
- 第二行包含 N 空格分隔值 B_i,代表城市的重要性 i. B_1, B_2, \ldots, B_N 都是不同的。
- 以下 M 线路提供道路信息。的 (2 + j)-第行表示有一条来自城市的单向道路 U_j 前往城市 V_j.
输出
输出 Takahashi 将城市标记为调查城市的顺序,在一行上以空格分隔。输出应准确包含 N 城市号码,每个号码来自 1 to N 只出现一次。
示例输入 1
5 5 3 5 1 4 2 1 2 1 3 2 4 2 5 4 3
示例输出 1
1 2 4 3 5
示例输入 2
4 0 2 4 3 1
示例输出 2
1 2 3 4
示例输入 3
8 8 4 7 2 8 1 6 3 5 1 2 1 4 2 3 2 5 4 6 6 7 7 8 3 8
示例输出 3
1 4 6 7 8 2 3 5
示例输入 4
10 9 5 10 3 8 1 9 2 7 4 6 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
示例输出 4
1 2 3 4 5 6 7 8 9 10
示例输入 5
1 0 1
示例输出 5
1