题号：NC219184
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
迷宫问题是一类非常有意思的问题，从其中延伸出来的知识也有很多，而寻找一条从起点到达终点的路径则是许多迷宫问题的最基本要求。现在李学长收到了贺学长发来的一个大小为n*m的迷宫，其中有可走的和不可走的。除此之外，这个迷宫与一般的迷宫有所不同，其中有一些特殊的可以走的点上有传送门，通过传送门可以到达其他的有传送门的点而不需要花费任何时间。现在给出迷宫的起点和终点，所走的只能是上下左右四个方向。李学长希望你告诉他从起点到终点需要花费的最短时间是多少。
输入描述:
第一行有一个正整数T（1<=T<=200)，代表T组测试用例。
对于每组测试用例：
第一行有两个正整数n和m（2<=n,m<=1000)，表示迷宫的大小。
之后是一个n×m的迷宫，其中：'S'表示起点，'E'表示终点，'#'表示不能走的点，'.'表示可以走的点，'*'表示传送阵。
题目保证T组测试用例n的总和不超过1000，m的总和不超过1000。
输出描述:
输出T行，每行按照格式（具体格式见样例）输出一个从起点到终点的最短时间。如果找不到一条从起点到终点的路，则输出 -1。