← 返回题目列表

AtCoder · abc289_b

D. 字母 V

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

分数: 200 点

问题陈述

学习 看文,高桥无法弄清楚单词的阅读顺序。 帮帮他吧!

有 N 整数来自 1 通过 N 按升序排列成行。
他们之间是 M “Re”标记。 的 i-第一个“Re”标记位于整数之间 a_i 和整数 (a_i + 1).

您阅读了每一个 N 通过以下过程整数一次。

  • 考虑一个无向图 G 与 N 顶点编号 1 通过 N 和 M 边缘。 的 i第一条边连接顶点 a_i 和顶点 (a_i+1).
  • 重复以下操作,直到没有未读的整数:
    • 让 x 是最小未读整数。 选择连接的组件 C 包含顶点 x,并读取其中包含的所有顶点的编号 C 按降序排列。

例如,假设整数和“re”标记按以下顺序排列:

image

(在这种情况下, N = 5, M = 3,和 a = (1, 3, 4).)
然后,读取整数的顺序确定为 2, 1, 5, 4,和 3,如下:

  • 首先,最小未读整数为 1,以及连接组件 G 包含顶点 1 有顶点 \lbrace 1, 2 \rbrace,所以 2 和 1 按此顺序读取。
  • 那么,最小未读整数为 3,以及连接组件 G 包含顶点 3 有顶点 \lbrace 3, 4, 5 \rbrace,所以 5, 4,和 3 按此顺序读取。
  • 现在所有整数都已读取,终止该过程。

鉴于 N, M,和 (a_1, a_2, \dots, a_M),打印读取命令 N 整数。

什么是连通分量? A 子图 图的 是从原始图中选择一些顶点和边得到的图。
据说有一张图 已连接 当且仅当可以通过边在图中的任意两个顶点之间移动。
A 连接的组件 是一个连通子图,不包含在任何更大的连通子图中。

约束

  • 1 \leq N \leq 100
  • 0 \leq M \leq N - 1
  • 1 \leq a_1 \lt a_2 \lt \dots \lt a_M \leq N-1
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
a_1 a_2 \dots a_M

输出

按以下格式打印答案,其中 p_i 是 i- 要读取的第一个整数。

p_1 p_2 \dots p_N

示例输入 1

5 3
1 3 4

示例输出 1

2 1 5 4 3

如问题陈述中所述,如果整数和“re”标记按以下顺序排列:

image

然后按以下顺序读取整数: 2, 1, 5, 4,和 3.


示例输入 2

5 0

示例输出 2

1 2 3 4 5

可能没有“re”标记。


示例输入 3

10 6
1 2 3 7 8 9

示例输出 3

4 3 2 1 5 6 10 9 8 7