Quái vật

Trong giờ học lập trình, FullHouse Dev được thầy giáo đưa ra một bài toán thú vị về mê cung. Các bạn được yêu cầu viết một chương trình để giúp nhân vật thoát khỏi mê cung có quái vật, khiến cả lớp vô cùng hứng thú với thử thách này.

Bài toán

Bạn và một số quái vật đang ở trong mê cung. Khi bạn di chuyển một bước theo một hướng nào đó, mỗi con quái vật cũng có thể đồng thời di chuyển một bước. Mục tiêu của bạn là đến được một ô nào đó ở biên của mê cung mà không bao giờ ở cùng ô với quái vật. Nhiệm vụ của bạn là xác định xem liệu mục tiêu này có khả thi hay không, và nếu có thì in ra đường đi có thể thực hiện được. Kế hoạch của bạn phải hoạt động trong mọi tình huống, ngay cả khi quái vật biết trước đường đi của bạn.

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): chiều cao và chiều rộng của bản đồ.
• \(n\) dòng tiếp theo, mỗi dòng chứa \(m\) ký tự mô tả bản đồ:
  • . (sàn)
  • # (tường)
  • A (điểm xuất phát)
  • M (quái vật) Trong đó có đúng một ký tự A trong input.

OUTPUT FORMAT:

• In ra "YES" nếu có thể đạt được mục tiêu, và "NO" nếu không thể.
• Nếu có thể đạt được mục tiêu, hãy in ra một ví dụ về đường đi hợp lệ (độ dài của đường đi và mô tả đường đi sử dụng các ký tự D, U, L, và R). Bạn có thể in ra bất kỳ đường đi nào, miễn là độ dài không vượt quá \(n \cdot m\) bước.

Ràng buộc:

• \(1 \leq n,m \leq 1000\)

Ví dụ

INPUT

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

OUTPUT

YES
5
RRDDR

Giải thích

Trong ví dụ này, người chơi có thể di chuyển theo hướng: phải, phải, xuống, xuống, phải (RRDDR) để thoát khỏi mê cung an toàn mà không bị quái vật bắt được.