/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
高橋君は漢文の勉強をしていて、漢字を読む順番が分からず困っています。高橋君を助けましょう！
1 から N までの N 個の整数が小さい方から順に 1 列に並んでいます。
整数の間に M 個の「レ」が挟まっています。i 個目の「レ」は、整数 a_i と整数 a_i + 1 の間にあります。
あなたは次の手順に従って、N 個の整数を 1 回ずつ全て読みます。
- まず、頂点に 1 から N までの番号がついた 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 であり、グラフ 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 個の整数を読む順番を出力してください。
連結成分とは
あるグラフの 部分グラフ とは、元のグラフのいくつかの頂点といくつかの辺を選んでできるグラフのことをいいます。グラフが 連結 であるとは、グラフに含まれるすべての頂点同士が辺を経由して互いに行き来できることをいいます。
連結成分 とは、連結な部分グラフのうち、そのグラフを含んだより大きい連結な部分グラフが存在しないものをいいます。
制約
- 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
問題文の例にある通り、整数と「レ」が
という順で並んでいる場合は 2, 1, 5, 4, 3 の順で読みます。
入力例 2
5 0
出力例 2
1 2 3 4 5
「レ」が存在しない場合もあります。
入力例 3
10 6 1 2 3 7 8 9
出力例 3
4 3 2 1 5 6 10 9 8 7
Score : 200 points
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