V

题目描述

学习 Kanbun 时，高桥在确定单词的阅读顺序上遇到了困难。帮帮他吧！

有 $N$ 个从 $1$ 到 $N$ 的整数按升序排列。
它们之间有 $M$ 个“レ”标记。第 $i$ 个“レ”标记在整数 $a_i$ 和整数 $(a_i + 1)$ 之间。
你按以下程序将每个 $N$ 个整数读一次。

考虑一个有 $N$ 个顶点、编号为 $1$ 到 $N$、并有 $M$ 条边的无向图 $G$。第 $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$ 的图 $G$ 的连通分量的顶点为 $\lbrace 1, 2 \rbrace$，因此按顺序读出 $2$ 和 $1$。 然后，最小的未读整数是 $3$，且包含顶点 $3$ 的图 $G$ 的连通分量的顶点为 $\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$

5 3
1 3 4

2 1 5 4 3

5 0

1 2 3 4 5

10 6
1 2 3 7 8 9

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 \lt a_2 \lt \dots \lt a_M \leq N-1$ 输入中的所有值均为整数。如问题描述所示，如果整数和“レ”标记按如下顺序排列： 则整数的读取顺序为：$2, 1, 5, 4,$ 和 $3$.
可能没有“レ”标记。

标签: AtCoder|abc289B

来源

AtCoder|abc289B