61.5% (16/26)

27.6% (27/98)

# Description

TAs are now developing a brand new version of robot that can run through a given maze as fast as possible, but we are facing a serious problem about finding the path from begin to end. Since you are so clever, please help us to solve this problem.
Notice that only vertical and horizontal steps are valid.

# Input Format

First line of input is a number $n \ (n \leq 25)$, which represents the size of maze.
Following is an $n \times n$ matrix which is the maze itself, with $w$ and $r$ represent walls and road respectively.

# Output Format

Couple lines to show the path from begin$(0, 0)$/upper-left to the end$(n-1, n-1)$/bottom-right.
Each line should have format $x \ y$, with $x$ represents horizontal axis and $y$ represents vertical one.

5
r w r r r
r r r w r
w w w r r
r r w r w
w r r r r

0 0
0 1
1 1
2 1
2 0
3 0
4 0
4 1
4 2
3 2
3 3
3 4
4 4

# Hints

Notice that there is only a single path from begin to end, so you do not need to concern about cases of more than one path.