Untitled

#include <bits/stdc++.h>
 
using namespace std;
 
void File() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
#ifdef MON
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("errors.txt", "w", stderr);
#else
#endif
}
 
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
char di[] = {'D', 'U', 'R', 'L'};
int n, m;
char a[1001][1001];
int par[1001][1001][2];
int lvl[1001][1001][2];
bool vis[1001][1001][2];
queue<pair<int, int>> q[2];
 
void bfs(int id) {
    while (!q[id].empty()) {
        int i = q[id].front().first, j = q[id].front().second;
        q[id].pop();
        for (int k = 0; k < 4; ++k) {
            int ni = i + dx[k], nj = j + dy[k];
            if (ni >= 0 && ni < n && nj >= 0 && nj < m && a[ni][nj] != '#' && !vis[ni][nj][id]) {
                q[id].push({ni, nj});
                lvl[ni][nj][id] = lvl[i][j][id] + 1;
                vis[ni][nj][id] = true;
                par[ni][nj][id] = k;
            }
        }
    }
}
 
int main() {
    File();
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
            if (a[i][j] == 'A') {
                q[0].push({i, j});
                vis[i][j][0] = true;
                lvl[i][j][0] = 0;
                par[i][j][0] = -1;
            } else if (a[i][j] == 'M') {
                q[1].push({i, j});
                vis[i][j][1] = true;
                lvl[i][j][1] = 0;
            }
        }
    }
    bfs(0);
    bfs(1);
    bool can = false;
    int edI, edJ;
    for (int i: {0, n - 1}) {
        for (int j = 0; j < m; ++j) {
            if ((vis[i][j][0] && lvl[i][j][0] < lvl[i][j][1]) || (!vis[i][j][1] && vis[i][j][0])) {
                can = true;
                edI = i, edJ = j;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j: {0, m - 1}) {
            if ((vis[i][j][0] && lvl[i][j][0] < lvl[i][j][1]) || (!vis[i][j][1] && vis[i][j][0])) {
                can = true;
                edI = i, edJ = j;
            }
        }
    }
    if (can) {
        cout << "YES\n";
        // print path
        int ni = edI, nj = edJ;
        vector<char> path;
        while (par[ni][nj][0] != -1) {
            // ni = i + dx[k];
            // ni - dx[k] = i;
            int k = par[ni][nj][0];
            path.push_back(di[k]);
            ni = ni - dx[k], nj = nj - dy[k];
        }
        reverse(path.begin(), path.end());
        cout << path.size() << "\n";
        for (auto &c: path) cout << c;
    } else cout << "NO\n";
    return 0;
}