B :: BFS

Time Limit: 10 Seconds    Memory Limit: 32768 KB

مدیو جادوگر بزرگ که از ابتدای تولد روح سارگراس در وجود وی رخنه کرده بود، به مرز جنون رسیده‌است. وی خادگار (جادوگر جوان دست‌آموز) را در زندان اسیر کرده‌است تا نقشه‌های شیطانی وی برملا نشود. گارونا (جنگجوی نیمه‌ارک- نیمه‌انسان) به زیرکی متوجه محل زندان و نقشه‌ی آن می‌شود. این زندان از چند طبقه تشکیل شده‌است، هر طبقه به صورت یک مستطیل است که هر خانه‌ی آن می‌تواند پر یا خالی باشد. خادگار می‌تواند به خانه‌های خالی مجاور خود (شرق، غرب، جنوب، شمال، بالا و پایین) برود و این جا‌به‌جایی یک دقیقه طول می‌کشد. گارونا متوجه می‌شود در یک طبقه راهی به بیرون وجود دارد. به او کمک کنید تا ببیند آیا می‌تواند خادگار را به این راه فرار برساند یا خیر. در صورتی که می‌تواند برساند کمترین زمان برای رسیدن چقدر است.

Input

    ورودی از چند نمونه تشکیل شده‌است. خط اول هر نمونه از ۳ عدد L و R و C تشکیل می‌شود که بیش‌تر از ۳۰ نیستند. L تعداد طبقات زندان، R‌ تعداد سطر‌ها و C تعداد ستون‌های هر طبقه است. پس از این خط، مشخصات L طبقه می‌آید که به صورت یک مستطیل R در C است. هر خانه اگر  # باشد یعنی پر است و اگر . باشد یعنی خالی است. S مکان اولیه‌ی خادگار را نشان می‌دهد و E نشان‌دهنده‌ی خانه‌ی فرار است. ورودی‌ها با ۳ تا صفر پایان می‌یابد.

Output

برای هر نمونه در صورتی که می‌توانست فرار کند، بنویسید "Escaped in x minute(s).” که x حداقل زمانی است برای فرار الزامی است. در غیر این صورت بنویسید “Trapped!”.

Sample Input

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

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

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

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

0 0 0

Sample Output

Escaped in 11 minute(s).
Trapped!
Submit