Graph Algorithms

You are given a map of a labyrinth, and your task is to find a path from start to end. You can walk left, right, up and down.

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 labyrinth. Each character is $.($floor$),$ # $($wall$),$ A $($start$),$ or $($end$).$ There is exactly one A and one B in the input.

Output

First print "YES", if there is a path, and $"$NO$"$ otherwise.

Example

Input:

$58$

########

#$.$A#$...$#

#$.$##$.$#B#

#$.......$#

########

Output:

YES

N$.$B: Solve using Breadth First Search $($BFS$)$ Algorithm considering the adjacent cells are adjacent nodes.

Use Java programming language.