You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-1194 题。

题目描述

你和一些怪物在一个迷宫中。当你在迷宫中朝某个方向走一步时，每个怪物也可能同时走一步。你的目标是到达边界的一个格子，并且在这个过程中不能与任何怪物站在同一个格子上。

你的任务是判断是否可以实现这个目标，如果可以，则输出一条你可以走的路径。你的路径计划必须适用于任何情况，即使怪物事先知道你的路径。

输入格式

第一行包含两个整数 $n$ 和 $m$：表示地图的高度和宽度。

接下来的 $n$ 行，每行 $m$ 个字符，描述地图的情况。每个字符是：.（空地），#（墙壁），A（起始点），M（怪物）。

输入中恰好有一个 A。

输出格式

如果目标可以达成，输出 YES，否则输出 NO。

如果目标可以达成，还需要输出一个有效的路径，路径的长度和描述使用字符 D（下）、U（上）、L（左）、R（右）。你可以输出任何一条路径，只要其长度不超过 $n \times m$ 步。

样例

5 8
########
#M..A..#
#.#.M#.#
#M#..#..
#.######

YES
5
RRDDR

说明/提示

$1 \le n,m \le 1000$。