AT_c_league2026_1_a Polish and Slide

$ N\times N $ のマスからなる盤面がある。 左上のマスの座標を $ (0,0) $ とし、そこから下に $ i $ マス、右に $ j $ マス進んだ位置のマスの座標を $ (i,j) $ とする。 あなたは初期位置 $ (i_0, j_0) $ におり、指定された目的地 $ (i_1, j_1), \dots, (i_{M-1}, j_{M-1}) $ をこの順番で訪れたい。 各ターンでは、以下のいずれかの行動を 1 つ選んで実行できる。 - **磨く:** 現在位置のマスをピカピカに磨き上げる。初期状態ではどのマスも磨かれていない。既に磨いたマスに対してこの操作を行っても何も変化しない。 - **滑る:** 上下左右の方向 $ d $ を指定し、盤面外に出ようとするか、磨かれていないマスに到達するまで、その方向への移動を繰り返す。より詳細には、以下の繰り返しを行う。 1. $ d $ 方向に隣接するマスが盤面外である場合、その場にとどまり繰り返しを終了する。 2. $ d $ 方向に隣接するマスが磨かれていない場合、隣接マスに移動して繰り返しを終了する。 3. $ d $ 方向に隣接するマスが磨かれている場合、隣接マスに移動して繰り返す。  「滑る」による移動中に、次に訪れるべき目的地のマスに到達した、または通過した場合、その時点でその目的地を訪れたものとみなす。同じ「滑る」の移動中に複数の目的地を指定された順番通りに通過した場合、それらはすべて訪れたものとみなされる。 一方、まだ訪れる順番ではない目的地のマスに到達した、または通過しても、その時点では訪れたものとはみなされない。その目的地を訪れる順番になった後に、改めてそのマスに到達するか通過する必要がある。 行動は最大で $ 10000 $ ターンまで行える。 できるだけ少ないターン数ですべての目的地を順に訪れるような行動列を求めよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ i_0 $ $ j_0 $ $ \vdots $ $ i_{M-1} $ $ j_{M-1} $ - すべてのテストケースにおいて、 $ N=20 $ 、 $ M=100 $ で固定されている。 - 初期位置および目的地の座標 $ (i_k,j_k) $ は、 $ 0 \leq i_k, j_k \leq N-1 $ を満たす整数であり、すべて互いに異なる。

各ターンの行動を、以下のようにアルファベット 1 文字で表す。 - **磨く:** `P` - **滑る:** 滑る方向に応じて、上：`U`、下：`D`、左：`L`、右：`R` ターン数を $ T $ 、 $ t $ ターン目の行動を表す文字を $ a_t $ としたとき、以下の形式で標準出力に出力せよ。 > $ a_0 $ $ \vdots $ $ a_{T-1} $ [例を見る](https://img.atcoder.jp/c-league2026-1/LG9EG0CV.html?lang=ja&seed=0&output=sample)

### 得点 出力した行動列のターン数を $ T $ としたとき、 $ 10000-T $ の得点を得る。 すべての目的地を順に訪れることができなかった場合、WA となる。 テストケースは全部で 100 個あり、各テストケースの得点の合計が提出の得点となる。 1 つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定が WA または TLE となる。 ### 入力生成方法 初期位置および目的地は、以下の手順に従って生成される。 まず、すべての $ N^2 $ 個のマスの座標をランダムな順序に並び替える。 並び替えた座標列のうち、先頭から $ M $ 個を順に $ (i_0,j_0), (i_1,j_1), \dots, (i_{M-1},j_{M-1}) $ として採用する。 ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](https://img.atcoder.jp/c-league2026-1/LG9EG0CV.html?lang=ja): ローカル版より高性能でアニメーション表示と手動プレイが可能です。 - [ローカル版](https://img.atcoder.jp/c-league2026-1/LG9EG0CV.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/c-league2026-1/LG9EG0CV_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、チーム外とのビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。