题目描述

小码哥走入了一个神奇的迷宫，这个迷宫的大小为$N\times M$。迷宫由普通房间，陷阱房间，传送门房间组成。陷阱房间不能进入，普通房间和传送门房间可以进入。一个房间和与其相邻的$4$个房间之间有门相连。传送门则连接两个传送门房间，可以进行双向传送，也可以选择通过门进入相邻的房间。可以认为，小码哥通过一扇门到达另一个房间的时间，和通过传送门到达另一个房间的时间是相同的，都为$1$分钟。小码哥用魔法地图提前得知了迷宫的构造，他想知道自己最快需要几分钟走出迷宫，或者不能走出迷宫。

输入格式

第一行输入两个整数$N,M$。 接下来$N$行，每行一个长度为$M$的字符串，描述了迷宫的情况。 字符#表示陷阱房间，字符.表示普通房间，字符s表示起点房间，字符e表示终点房间，大写字母字符则表示传送门房间，相同的字母表示这两个房间之间有传送门连接。

输出格式

输出一行一个整数，表示最短时间。如果不能从起点走到终点，输出-1。

样例输入 #1

6 6
######
#s..##
#.#A##
#.#.##
#.A.##
#e.###

样例输出 #1

4

说明/提示

对于100%的数据，有$2\leq N,M\leq 100$，且s和e只出现一次，每个大写字母只出现$0$或$2$次。