Problem: monsters

Monsters

Two monsters are placed in a NxN maze. The good monster is placed at the top left corner, whereas the evil one is placed at the bottom right corner of the maze. Each maze cell contains either a 1 or a 0. The monsters walk only up, down, left and right (NOT diagonally), in cells which contain a 1. The monsters are met, if they stand on the same cell. You must find the minimum number of steps each monster should perform in order to meet. Note, that at each turn, both monsters should perform a step (i.e. it is not allowed for a monster to stay at the same position, while the other has performed a step). Also, depending on the maze content, the two monsters may never meet.

Input
Your program should read the input data from standard input as follows:

• the first line of the input file contains a positive integer N<=20, designating the side of the square maze.
• each of the subsequent N lines contain N numbers separated by a space character. Each number is a 0 or a 1. These lines are used to represent the maze.

Output

Your program should write the output to the standard output as follows:

• if it is impossible for the two monsters to meet, the first line of the file should contain the string ``NOPATH''.
• if there is a ``meeting'' path, then the first line should contain the minimum number of steps that the monsters should perform in order to meet.
• the next line contains a set of characters that indicates the path that the good monster should follow. These characters must be either U (for up), D (for down), L (for left) and R (for right). No space character should be placed between these characters.
• the next line contains a set of characters that indicates the path that the evil monster should follow. Again, these characters must be U, D, L, or R, whereas no space should be placed between these characters.

Sample input:

5
1 1 1 1 0
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 1 1 1 1

Sample output:

4
DDDD
LLLL

Sample input:

5
0 0 0 0 1
0 0 0 1 0
0 0 1 0 0
0 1 0 0 0
1 0 0 0 0

Sample output:

NOPATH