Röjarrobotar

En grupp gymnasiestudenter har nyligen experimenterat med robotar. De hade länge fruktat att denna dag skulle komma, men nu har deras värsta mardrömar till slut slagit in: robotarnas artificiella intelligens har blivit så avancerad att de börjat tänka själva, och de tänker självfallet förstöra mänskligheten.

Turligt nog finns det fortfarande hopp eftersom robotarna fortfarande är inne i skolan, och det är inte känt huruvida de faktiskt kan komma ut. Din uppgift är att, givet skolans planritning och robotarnas position, avögra om någon av robotarna kan fly, eller om de alla är fast inne i skolan.

Planritningen är en $n \times m$ matris som består av följande tecken:

• ‘.’ betecknar en tom golvruta.

• ‘#’ betecknar en vägg eller en stängd dörr.

• ‘X’ betecknar en robot.

Robotar kan köra mellan rutor som har en gemensam kant (men inte digonalt).

En robot kan fly från skolan om den kan nå kanten av våningsplanet.

Indata

Den första raden i indatan innehåller två heltal $n, m$. Sedan följer $n$ rader, som alla innehåller $m$ tecken. Dessa beskriver planritningen på sättet som definerades ovan. Du kan anta att inga robotar eller väggar är på kanten av våningsplanet.

Utdata

Du ska skriva ut en rad som innehåller “Death to humans” om någon av robotarna kan fly, annars ska du skriva ut “We are safe”.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

8 10
..........
.########.
.#.X....#.
.######.#.
.#..#...#.
....#X..#.
.########.
..........

We are safe

13 13
.............
.###########.
.#.........#.
.#.#######.#.
.#.#.....#.#.
.#.#.###.#.#.
.#.#..X#.#.#.
.#.#####.#.#.
.#.......#.#.
.#########.#.
.#.........#.
.#.#########.
.............

Death to humans

5 5
.....
..#..
.#X#.
..#..
.....

We are safe