void dfs(int m[MAX][MAX], int i, int j, int n, vector<string>&ans, string temp){

    if(i<0 || j < 0 || i>=n || j >=n || m[i][j]==0 )return;
      if(i==n-1 && j == n-1 ){
        ans.push_back(temp);
        return;
    }

    if(m[i][j] == 0) return;
    m[i][j]=0;

    dfs(m, i+1, j, n, ans, temp+"D");
    dfs(m, i, j+1, n, ans, temp+"R");
    dfs(m, i-1, j, n, ans, temp+"U");
    dfs(m, i, j-1, n, ans, temp+"L");
    m[i][j]=1;

}

vector<string> printPath(int m[MAX][MAX], int n) {
    // Your code goes here
    if(n==0)return {};
    if(m[0][0]==0 || m[n-1][n-1]==0)return {};

    vector<string>ans;
    dfs(m, 0, 0, n, ans, "");
    sort(ans.begin(), ans.end());
    return ans;
}