← 返回题目列表

AtCoder · awc0100_h

H. 城市旅游调查

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

分数: 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 通过重复以下过程对所有城市进行调查。最初,所有城市都没有进行调查。

  1. 确定起始城市。 首次游览,起始城市为 city 1。对于后续的每次游览,起始城市是重要性最高的未调查城市。
  2. 从出发城市进行游览。 首先,标记调查的起始城市。然后,重复以下操作:
  • 如果从当前城市单条道路直达的城市中至少存在一个未调查的城市,则移动到具有该城市的城市 最高重要性 其中 ,并将该城市标记为调查对象。
  • 如果当前城市单条道路可直达的城市中不存在未调查的城市(包括根本不存在可达城市的情况), 结束本次游览.
  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