AT_abc289_b [ABC289B] レ

[problemUrl]: https://atcoder.jp/contests/abc289/tasks/abc289_b > 高橋君は漢文の勉強をしていて、漢字を読む順番が分からず困っています。高橋君を助けましょう！ $ 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 $ 個の整数を読む順番を出力してください。 連結成分とは あるグラフの **部分グラフ** とは、元のグラフのいくつかの頂点といくつかの辺を選んでできるグラフのことをいいます。 グラフが **連結** であるとは、グラフに含まれるすべての頂点同士が辺を経由して互いに行き来できることをいいます。 **連結成分** とは、連結な部分グラフのうち、そのグラフを含んだより大きい連結な部分グラフが存在しないものをいいます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ a_1 $ $ a_2 $ $ \dots $ $ a_M $

答えを以下の形式で出力せよ。ここで $ p_i $ は、$ i $ 番目に読まれる整数を意味する。 > $ p_1 $ $ p_2 $ $ \dots $ $ p_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 $ - 入力される値は全て整数 ### Sample Explanation 1 問題文の例にある通り、整数と「レ」が !\[image\](https://img.atcoder.jp/ghi/abc289\_4328a29fa11f2f7fe51962c84eb3f7d8530b6a7eb40438a04b652a0771430765.jpg) という順で並んでいる場合は $ 2,\ 1,\ 5,\ 4,\ 3 $ の順で読みます。 ### Sample Explanation 2 「レ」が存在しない場合もあります。