# 【題解】Codeforces 1316D. Nash Matrix

```#include <iostream>
#include <queue>
using namespace std;
#define F first
#define S second

int n, x[1005][1005], y[1005][1005], dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
char ans[1005][1005], dc[4] = {'R', 'L', 'D', 'U'};

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
queue <pair<int, int> > q;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
cin >> x[i][j] >> y[i][j];
if (x[i][j] == i && y[i][j] == j){
q.push({i, j});
ans[i][j] = 'X';
}
}
}
pair<int, int> p;
while (!q.empty()){
p = q.front();
q.pop();
if (p.F != 1){
if (x[p.F-1][p.S] == x[p.F][p.S] && y[p.F-1][p.S] == y[p.F][p.S]){
if (!ans[p.F-1][p.S]){
ans[p.F-1][p.S] = 'D';
q.push({p.F-1, p.S});
}
}
}
if (p.F != n){
if (x[p.F+1][p.S] == x[p.F][p.S] && y[p.F+1][p.S] == y[p.F][p.S]){
if (!ans[p.F+1][p.S]){
ans[p.F+1][p.S] = 'U';
q.push({p.F+1, p.S});
}
}
}
if (p.S != 1){
if (x[p.F][p.S-1] == x[p.F][p.S] && y[p.F][p.S-1] == y[p.F][p.S]){
if (!ans[p.F][p.S-1]){
ans[p.F][p.S-1] = 'R';
q.push({p.F, p.S-1});
}
}
}
if (p.S != n){
if (x[p.F][p.S+1] == x[p.F][p.S] && y[p.F][p.S+1] == y[p.F][p.S]){
if (!ans[p.F][p.S+1]){
ans[p.F][p.S+1] = 'L';
q.push({p.F, p.S+1});
}
}
}
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
if (x[i][j] == -1){
for (int k = 0; k < 4; k++){
if (x[i+dx[k]][j+dy[k]] == -1){
ans[i][j] = dc[k];
break;
}
}
}
}
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
if (ans[i][j] == 0){
cout << "INVALID\n";
return 0;
}
}
}
cout << "VALID\n";
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
cout << ans[i][j];
}
cout << "\n";
}
}
```