THE JUST LABYRINTH

In a game show, players are placed in a labyrinth from which they must escape. The labyrinth consists of N×M rooms arranged in a rectangular layout. Each room has a puzzle, and if the player solves it, a door opens leading to a specific neighboring room (up, down, left, or right). If a room is on the perimeter of the labyrinth and a door opens outward, the player exits and wins.

The dimensions of the labyrinth and the position of the exit door for each room are known from the beginning. In each room, the door is marked with one of the letters "U" (up), "D" (down), "L" (left), or "R" (right). Therefore, if a player starts from any initial room and solves the puzzles in the rooms they visit in order, the path they will follow is specific.

Unfortunately for the players, it's possible that the exit doors are positioned so that from some initial rooms, it is impossible to exit the labyrinth! Consider the example below. The arrows on the right side of the diagram show the path of the players from each room.

If a player starts from an initial room marked in yellow, they will get stuck in a circular path and will never be able to exit the labyrinth, no matter how many puzzles they solve. On the other hand, they will be able to exit from the remaining rooms if they solve the required puzzles.

The game show hosts want their game to be fair, meaning the initial rooms from which players cannot win, no matter how many puzzles they solve, should be few. Help them count these rooms!

Problem

Develop a program in one of the IOI languages (PASCAL, C, C++, Java) that reads the labyrinth and prints the number of initial rooms from which players cannot win.

Input Files:

The input files with the name fairmaze.in are text files with the following structure: The first line contains two integers N and M, the dimensions of the maze (rows and columns, respectively). Each of the next N lines represents a row of the maze and contains exactly M characters, each of which is one of the letters "U," "D," "L," or "R." The letter corresponding to each room signifies the position of the exit door for that room.

Output Files:

The output files with the name fairmaze.out are text files with the following structure. They contain exactly one line that contains an integer: the number of initial rooms from which players cannot win, no matter how many puzzles they solve.

Constraints:

• 1 ~\le~ Ν ~\le~ 1.000
• 1 ~\le~ M ~\le~ 1.000

Examples of Input - Output Files:

STDIN (fairmaze.in)

3 3
ULD
LUD
LRL

STDOUT (fairmaze.out)

4

Explanation:

The example is that of the above diagram. There are 4 rooms (marked in yellow in the diagram) from which players cannot win.

Notes:

Formatting: In both the input and the output, each line terminates with a newline character.
Maximum execution time: 1sec.
Maximum available memory: 64MB.
Headers in the source code: At the beginning of your source code, you should use the following headers.

(* USER: username
LANG: PASCAL
TASK: fairmaze *)

for PASCAL coders

/* USER: username
LANG: C
TASK: fairmaze */

for C coders

/* USER: username
LANG: C++
TASK: fairmaze */

for C++ coders

/* USER: username
LANG: Java
TASK: fairmaze */

for Java coders

# USER: username
# LANG: Python
# TASK: fairmaze

for Python coders