Kaotikus labirintus

Guest 2019 is lost and can't find the park exit. – szólt az értesítés Viktor kedvenc számítógépes játékában, a RollerCoaster Tycoonban. A Chris Sawyer által 1999-ben elindított, immár 20 éves vidámparképítő játék generációknak okozott felejthetetlen élményt. Ennek ellenére mindenkiben rémálmot vált ki még ma is az, amikor a látogatók eltévednek a park bonyolult járdarendszerein.

Viktor nemrég rátalált a kedvenc játéka telepítőjére, és ügyes programozóként egy nagyszerű terv jutott az eszébe. Visszafejtette a játék C nyelvű forráskódját, és elkezdte a labirintus attrakció (a játékban Hedge Maze) sorait átírni úgy, hogy az teljesen abszurd módon működjön. Belépéskor minden látogató a labirintus egy véletlen pontján találja magát, a kijutáshoz pedig meg kell keresnie a kijárathoz tartozó mezőt. A labirintusban lévő látogató minden lépéssel pontosan egy mezőt halad valamelyik olyan mezőre, melynek pontosan egy oldala közös a jelenlegi mezője oldalaival. Ugyanakkor a látogató teleportálhat a labirintus szélein: ekkor egy sor jobb szélső mezőjéből az azonos sor bal szélső mezőjére, egy sor bal szélső mezőjéről az azonos sor jobb szélső mezőjére, egy oszlop felső mezőjéről az azonos oszlop alsó mezőjére, míg egy oszlop alsó mezőjéről az azonos oszlop felső mezőjére is kerülhet. Egy tényezőn Viktor sem változtatott: a falat tartalmazó mezőkre továbbra sem léphetünk.

A bemenet specifikációja

A labirintus minden esetben téglalap alakú. A bemenet első sorában két egész szám szerepel, egyetlen szóközzel elválasztva egymástól: az első (N) a sorok száma, míg a második (M) az oszlopok száma (2 ≤ N, M ≤ 100). Az első sort pontosan N darab további sor követi, melyek egyenként M darab karaktert tartalmaznak. A szabad mezőket a '.' (pont), míg a falat az 'x' (kis x betű) karakter jelöli. A kiindulás helyét az 'S' karakter, míg a kijárat helyét az 'E' karakter jelöli.

A kimenet specifikációja

A programnak pontosan egy sort kell a kimenetre írnia. Amennyiben a látogató el tudja érni a kijáratot, és ezt optimálisan N lépésben tudja megtenni, úgy a „Guest 2019 needs N steps to find the maze exit.” sztring kerüljön a kimenetre! Abban az esetben pedig, ha a kijárat elérhetetlen helyen lenne, a „Guest 2019 cannot find the maze exit.” sort írd ki!