Twitch Plays Pokemon

Twitch Plays Pokemon is a meme that spread on the livestreaming platform Twitch. Viewers type commands in chat, and the game applies each command to control the character. Because thousands of viewers type at once, the chat order gets scrambled and it is hard to steer the character the way you want. That chaos is what makes Twitch Plays Pokemon appealing.

The game takes place in an $N\times N$ grid maze. Each cell is either empty or a wall. The character starts on an empty cell and must reach a destination on another empty cell. Viewers can enter one of U, D, L, R per command, which moves the character one cell up, down, left, or right. If a command tells the character to move into a wall or outside the maze, the character stays put. As soon as the character reaches the destination, it escapes the maze and ignores any further commands.

One night, Dalgu and Phoenix joined the game and together got the character out of the maze. Unfortunately, nobody recorded that moment. The host Yuni can check each viewer's chat log in time order, but cannot tell how the two viewers' messages are ordered relative to each other.

Arrange the chat messages of Dalgu and Phoenix in a suitable order. Find the minimum number of commands needed for the character to escape the maze.

The first line contains an integer $N$, the size of the maze. $(2\le N\le 20)$

The next $N$ lines each contain a string of length $N$ describing the maze. Each character means:

• .: empty cell
• #: wall
• S: starting cell of the character (exactly one)
• E: destination cell the character must reach (exactly one)

The next line contains Dalgu's commands in the order he typed them.

The line after that contains Phoenix's commands in the order she typed them.

Each command string has length between $1$ and $100$, inclusive, and consists only of U, D, L, R.

Print the minimum number of commands needed for the character to escape the maze when Dalgu's and Phoenix's chats are arranged in a suitable order.

If no arrangement of the chats lets the character escape the maze (for example, because of a logging error), print -1.