G. Цивилизация

Карта разбита на клетки: . — поле, W — лес, # — вода. Переселенец ходит по клеткам, имеющим общую сторону. Вход в поле стоит одну единицу времени, вход в лес — две, в воду войти нельзя.

Найдите наименьшее время пути из начальной клетки в конечную и сам маршрут.

Веса рёбер здесь уже не единичные, и обычный обход в ширину не годится: очередь перестаёт быть упорядоченной по расстоянию. Но весов всего два, и это спасает — например, можно разбить вход в лес на два шага по единице и вернуться к обычному обходу.

Маршрут выводится буквами: N — вверх, E — вправо, S — вниз, W — влево. Маршрутов минимальной стоимости может быть несколько; выведите лексикографически наименьший в обычном порядке букв: E меньше N, N меньше S, S меньше W.

Первая строка содержит числа $N$ и $M$ ($1 \le N, M \le 500$), затем координаты начальной клетки $x_1$, $y_1$ и конечной $x_2$, $y_2$ (строка и столбец, нумерация с единицы).

Далее идут $N$ строк по $M$ символов. Начальная и конечная клетки не вода.

Если дойти нельзя, выведите $-1$.

Иначе в первой строке — наименьшее время, во второй — маршрут. Если начальная и конечная клетки совпадают, вторая строка пустая.