AT_abc289_b [ABC289B] レ

题目描述

高桥君正在学习汉文，但他不知道汉字的阅读顺序而感到困惑。让我们来帮助高桥君吧！

有 $N$ 个整数，从 $1$ 到 $N$，按从小到大的顺序排成一列。
在这些整数之间插入了 $M$ 个“レ”。第 $i$ 个“レ”插在整数 $a_i$ 和整数 $a_i+1$ 之间。

你需要按照以下步骤，依次读出这 $N$ 个整数，每个整数只读一次。

• 首先，考虑一个有 $N$ 个顶点、$M$ 条边的无向图 $G$，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $a_i$ 和顶点 $a_i+1$。
• 然后，重复以下操作，直到所有整数都被读完为止：
  • 在尚未被读过的整数中，选择最小的一个，记为 $x$。找到包含顶点 $x$ 的连通分量 $C$，将 $C$ 中所有顶点的编号按从大到小的顺序全部读出。

例如，整数和“レ”如下图所示：

（在此例中，$N=5,\ M=3,\ a=(1,3,4)$。）

此时，整数的阅读顺序如下：$2,\ 1,\ 5,\ 4,\ 3$。

• 首先，尚未被读过的最小整数是 $1$，包含顶点 $1$ 的连通分量为 $\lbrace 1,2 \rbrace$，因此按 $2,1$ 的顺序读出。
• 接下来，尚未被读过的最小整数是 $3$，包含顶点 $3$ 的连通分量为 $\lbrace 3,4,5 \rbrace$，因此按 $5,4,3$ 的顺序读出。
• 所有整数都已读完，操作结束。

给定 $N,\ M,\ (a_1,a_2,\dots,a_M)$，请输出 $N$ 个整数的阅读顺序。

连通分量的定义如下：
一个图的子图是从原图中选取一些顶点和一些边组成的图。
一个图是连通的，指的是图中任意两个顶点都可以通过边互相到达。
连通分量是连通的子图，并且不存在包含它的更大的连通子图。

输入格式

输入从标准输入中给出，格式如下：

$N$ $M$ $a_1$ $a_2$ $\dots$ $a_M$

输出格式

请输出答案，格式如下，其中 $p_i$ 表示第 $i$ 个被读出的整数。

$p_1$ $p_2$ $\dots$ $p_N$

输入输出样例 #1

输入 #1

5 3
1 3 4

输出 #1

2 1 5 4 3

输入输出样例 #2

输入 #2

5 0

输出 #2

1 2 3 4 5

输入输出样例 #3

输入 #3

10 6
1 2 3 7 8 9

输出 #3

4 3 2 1 5 6 10 9 8 7

说明/提示

数据范围

• $1 \leq N \leq 100$
• $0 \leq M \leq N-1$
• $1 \leq a_1 < a_2 < \dots < a_M \leq N-1$
• 输入的所有数均为整数

样例解释 1

如题目所述，若整数和“レ”按 的顺序排列，则阅读顺序为 $2, 1, 5, 4, 3$。

样例解释 2

也有可能不存在“レ”。

由 ChatGPT 4.1 翻译