Chef and Finding Direction

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef has a grid of size N * N with its rows numbered from 1 to N, and the columns also numbered from 1 to N. The cell at the ith row and the jth column is cell (i,j). From cell (i,j), you can go in one of the four directions U L D R (corresponding to up, left, down, right) to cells (i1,j), (i,j1), (i+1,j), (i,j+1) respectively, and of course you cannot go outside of the grid. However, with each cell, Chef is only allowed to go in some of the four directions (at least one), which is given by a string directs[i][j] containing only the characters U L D R denoting the directions Chef can go from cell (i,j).
Now, Chef wants to choose exactly one direction to go from each cell, so that from any cell in the grid, he can come back to same cell by following the chosen directions of the cells. Please help him!
Input
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the size of the grid.
N lines follow. Each line contains N spaceseparated strings denoting the given directions for that cell. The j^{th} string in the i^{th} line is directs[i][j].
Output
For each test case, output a single line containing "YES" (without quotes) if for each cell Chef can choose one and only one direction to go so that from every cell Chef can go back to that cell using chosen directions, "NO" (without quotes) otherwise.
If the answer is "YES", then you must print the chosen directions in the next N lines. Each line will contain N strings. The j^{th} string in the i^{th} line must consist of a single character: the direction chosen for cell (i,j).
Constraints
 1 ≤ T ≤ 50
 2 ≤ N ≤ 150
 1 ≤ length directs[i][j] ≤ 4
Subtasks
Subtask #1: (10 points)
 2 ≤ N ≤ 5
 1 ≤ length directs[i][j] ≤ 2
 2 ≤ N ≤ 12
 2 ≤ N ≤ 50
Subtask #4: (40 points)
 Original constraints
Example
Input: 2 2 RD D UR UL 3 RD LR DL RU LU LDU U UL L Output: YES R D U L NO
Explanation
Example case 1. Chef can keep the direction R for cell (1, 1), D for (1, 2), U for (2, 1) and L for (2, 2). Then he can go (1,1) > (1,2) > (2,2) > (2,1) > (1,1). It means that from any cell he always can go back to that cell.
Example case 2. There is no way to keep only 1 direction for each cell to satisfy the condition.
Author:  lexman 
Editorial  https://discuss.codechef.com/problems/CHEFAFD 
Tags  dec16, hamiltonian, hopcroftkarp, lexman, matching, maxflow 
Date Added:  17092016 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 