题目描述

你被困在一个三维的空间中，现在要寻找最短路径逃生！

空间由立方体单位构成。每次可以向上下、前后、左右移动一个单位，需要一分钟。不能对角线移动，且空间封闭。

判断是否存在逃出生天的可能性，如果存在，则输出所需的最短时间。

输入格式

输入包含若干个空间描述。

对于每个空间：

• 第一行三个整数 $L, R, C$，分别表示空间的高度、每层的行数和列数
• 接下来是 $L$ 层地牢的描述，每层有 $R$ 行，每行 $C$ 个字符
• 每层之后有一个空行
• 字符含义：
  • # 表示障碍，不可通过
  • . 表示空白，可通过
  • S 表示起点
  • E 表示终点

输入以 0 0 0 结束

输出格式

对于每个空间，输出一行：

• 如果可以到达终点，输出 Escaped in x minute(s).，其中 $x$ 为最短时间
• 如果无法到达终点，输出 Trapped!

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0

Escaped in 11 minute(s).
Trapped!

提示

样例 1 说明

对于第一个空间 ($L=3, R=4, C=5$)，一条可行的最短路径为：

$(1,1,1) \to (1,1,2) \to (1,1,3) \to (1,1,4) \to (1,1,5) \to (1,2,5) \to (1,3,5) \to (1,3,4) \to (1,4,4) \to (2,4,4) \to (2,4,5) \to (3,4,5)$

共需要 $11$ 分钟。

对于第二个空间 ($L=1, R=3, C=3$)，起点 S 和终点 E 被障碍物隔开，无法到达。

数据规模与约定

对于全部的测试点，保证 $1 \leq L, R, C \leq 30$。