Yi Kai has overslept and realized that he has very little time left to attend a very important event! Having recently moved, he takes out a map to navigate through his new neighbourhood to reach his destination. The map shows that the neighbourhood is arranged in a grid of size by , with a `.`

indicating a walkable path which takes 1 minute to walk across, and an `X`

indicating a building. He takes out his marker, looks around his surroundings, and marks his current position with an `s`

on the map. Then, he finds his destination, and marks an `e`

on it. He looks at the map again, but the number of possible routes to his destination overwhelms him! Help Yi Kai find out how much time he will need to reach his destination if he uses the shortest possible route!

(Inspired by Yi Kai oversleeping before previous NOI trainings)

#### Input

The first line will contain two integers, , and .
The next lines will contain characters each, one of `.`

, `X`

, `s`

or `e`

.

#### Output

A single integer, the minimum time he requires to reach his destination in minutes, or if it is not possible and he has to call for a helicopter.

#### Limits

#### Sample Input 1

```
4 4
s...
....
....
...e
```

#### Sample Output 1

`5`

#### Sample Input 2

```
3 4
XXXe
....
sXXX
```

#### Sample Output 2

`4`

## Comments

This comment is hidden due to too much negative feedback. Click here to view it.

How am I getting TLE with BFS? (https://dmoj.ca/src/2135683) Am I missing something?

`g[x][y] = 'X'`

should be`g[y][x] = 'X'`

.This comment is hidden due to too much negative feedback. Click here to view it.

Uh, to figure out the issue with your code...

Testing your code for AC

Oh ok.

How come C is disabled for this question?

its not.