- Time limit: 1.00 s
- Memory limit: 512 MB
Uolevi has been wandering around an abandoned warehouse recording his true crime podcast. Getting purposefully lost is part of the fun: now he just needs to figure a way out. Uolevi finds a map of the building on a wall. On the map, he can walk left, right, up and down. Help Uolevi find a way out or report that he is locked in for good.
Input
The first input line has two integers n and m: the height and width of the map.
Then there are n lines of m characters describing the warehouse. Each character is .
(floor), #
(wall), A
(Uolevi), or B
(exit). There is exactly one A
and one B
in the input.
Output
In the first line print "YES", if there is a way, and "NO" otherwise.
If there is a path, print the length of the shortest such path on the next line, and its description as a string consisting of characters L
(left), R
(right), U
(up), and D
(down) on another line. You can print any valid solution.
Constraints
- 1 \le n,m \le 1000
Example
Input:
5 8 ######## #.A#...# #.##.#B# #......# ##..####
Output:
YES 9 LDDRRRRRU