Score : $200$ points

问题描述

正在学习 汉文 的高桥在理解单词阅读顺序上遇到了困难，快来帮帮他！

有 $N$ 个从 $1$ 到 $N$ 的整数按升序排列成一行。
在这 $N$ 个整数之间有 $M$ 个“レ”标记。第 $i$ 个“レ”标记位于整数 $a_i$ 和整数 $(a_i + 1)$ 之间。

按照以下步骤依次读取这 $N$ 个整数：

• 考虑一个包含 $N$ 个顶点（编号为 $1$ 到 $N$）和 $M$ 条边的无向图 $G$。第 $i$ 条边连接顶点 $a_i$ 和顶点 $(a_i+1)$。
• 重复以下操作，直到没有未读整数：
  • 让 $x$ 为当前最小未读整数。选择包含顶点 $x$ 的连通分量 $C$，并按照降序读取该连通分量中所有顶点对应的数字。

例如，假设整数和“レ”标记按照以下顺序排列：

（在这个例子中，$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$ 个整数的顺序。

什么是连通分量？子图是指从原图中选取部分顶点和边所得到的图形。
若在一个图中，通过边可以到达任意两个顶点，则称该图为 连通 的。
连通分量 是指不包含在任何更大的连通子图内的连通子图。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Studying Kanbun, Takahashi is having trouble figuring out the order to read words. Help him out!

There are $N$ integers from $1$ through $N$ arranged in a line in ascending order.
Between them are $M$ "レ" marks. The $i$-th "レ" mark is between the integer $a_i$ and integer $(a_i + 1)$.

You read each of the $N$ integers once by the following procedure.

• Consider an undirected graph $G$ with $N$ vertices numbered $1$ through $N$ and $M$ edges. The $i$-th edge connects vertex $a_i$ and vertex $(a_i+1)$.
• Repeat the following operation until there is no unread integer:
  • let $x$ be the minimum unread integer. Choose the connected component $C$ containing vertex $x$, and read all the numbers of the vertices contained in $C$ in descending order.

For example, suppose that integers and "レ" marks are arranged in the following order:

(In this case, $N = 5, M = 3$, and $a = (1, 3, 4)$.)
Then, the order to read the integers is determined to be $2, 1, 5, 4$, and $3$, as follows:

• At first, the minimum unread integer is $1$, and the connected component of $G$ containing vertex $1$ has vertices $\lbrace 1, 2 \rbrace$, so $2$ and $1$ are read in this order.
• Then, the minimum unread integer is $3$, and the connected component of $G$ containing vertex $3$ has vertices $\lbrace 3, 4, 5 \rbrace$, so $5$, $4$, and $3$ are read in this order.
• Now that all integers are read, terminate the procedure.

Given $N, M$, and $(a_1, a_2, \dots, a_M)$, print the order to read the $N$ integers.

What is a connected component? A subgraph of a graph is a graph obtained by choosing some vertices and edges from the original graph.
A graph is said to be connected if and only if one can travel between any two vertices in the graph via edges.
A connected component is a connected subgraph that is not contained in any larger connected subgraph.

Constraints

• $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$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$

$a_1$ $a_2$ $\dots$ $a_M$

Output

Print the answer in the following format, where $p_i$ is the $i$-th integers to read.

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

Sample Input 1

5 3
1 3 4

Sample Output 1

2 1 5 4 3

As described in the Problem Statement, if integers and "レ" marks are arranged in the following order:

then the integers are read in the following order: $2, 1, 5, 4$, and $3$.

Sample Input 2

5 0

Sample Output 2

1 2 3 4 5

There may be no "レ" mark.

Sample Input 3

10 6
1 2 3 7 8 9

Sample Output 3

4 3 2 1 5 6 10 9 8 7

update @ 2024/3/10 12:04:10