package main
import (
"bufio"
"fmt"
"os"
)
type Item struct {
state int32
cost int64
}
type MinHeap struct {
items []Item
}
func (h *MinHeap) Push(x Item) {
h.items = append(h.items, x)
h.up(len(h.items) - 1)
}
func (h *MinHeap) Pop() Item {
n := len(h.items) - 1
h.items[0], h.items[n] = h.items[n], h.items[0]
x := h.items[n]
h.items = h.items[:n]
h.down(0, n)
return x
}
func (h *MinHeap) up(j int) {
for {
i := (j - 1) / 2
if i == j || h.items[j].cost >= h.items[i].cost {
break
}
h.items[i], h.items[j] = h.items[j], h.items[i]
j = i
}
}
func (h *MinHeap) down(i0, n int) {
i := i0
for {
j1 := 2*i + 1
if j1 >= n || j1 < 0 {
break
}
j := j1
if j2 := j1 + 1; j2 < n && h.items[j2].cost < h.items[j1].cost {
j = j2
}
if h.items[i].cost <= h.items[j].cost {
break
}
h.items[i], h.items[j] = h.items[j], h.items[i]
i = j
}
}
func (h *MinHeap) Len() int {
return len(h.items)
}
func main() {
scanner := bufio.NewScanner(os.Stdin)
scanner.Split(bufio.ScanWords)
if !scanner.Scan() {
return
}
n := 0
for _, c := range scanner.Text() {
n = n*10 + int(c-'0')
}
scanner.Scan()
m := 0
for _, c := range scanner.Text() {
m = m*10 + int(c-'0')
}
grid := make([]string, n)
var lr, lc, yr, yc, tr, tc int
for i := 0; i < n; i++ {
scanner.Scan()
grid[i] = scanner.Text()
for j := 0; j < m; j++ {
switch grid[i][j] {
case 'Y':
yr, yc = i, j
case 'B':
lr, lc = i, j
case 'T':
tr, tc = i, j
}
}
}
dr := []int{-1, 1, 0, 0}
dc := []int{0, 0, -1, 1}
moveChar := []byte{'n', 's', 'w', 'e'}
pushChar := []byte{'N', 'S', 'W', 'E'}
const MAX_STATES = 2560000
dist := make([]int64, MAX_STATES)
for i := range dist {
dist[i] = 2e18
}
prev := make([]int32, MAX_STATES)
for i := range prev {
prev[i] = -1
}
action := make([]byte, MAX_STATES)
startState := int32(lr*64000 + lc*1600 + yr*40 + yc)
dist[startState] = 0
heap := &MinHeap{}
heap.Push(Item{state: startState, cost: 0})
found := false
var targetState int32
for heap.Len() > 0 {
u := heap.Pop()
if dist[u.state] < u.cost {
continue
}
clr := int(u.state / 64000)
clc := int((u.state / 1600) % 40)
if clr == tr && clc == tc {
found = true
targetState = u.state
break
}
cyr := int((u.state / 40) % 40)
cyc := int(u.state % 40)
for i := 0; i < 4; i++ {
nyr := cyr + dr[i]
nyc := cyc + dc[i]
if nyr < 0 || nyr >= n || nyc < 0 || nyc >= m {
continue
}
if grid[nyr][nyc] == 'X' {
continue
}
if nyr == clr && nyc == clc {
nlr := clr + dr[i]
nlc := clc + dc[i]
if nlr < 0 || nlr >= n || nlc < 0 || nlc >= m {
continue
}
if grid[nlr][nlc] == 'X' {
continue
}
nstate := int32(nlr*64000 + nlc*1600 + clr*40 + clc)
ncost := u.cost + 10000001
if ncost < dist[nstate] {
dist[nstate] = ncost
prev[nstate] = u.state
action[nstate] = pushChar[i]
heap.Push(Item{state: nstate, cost: ncost})
}
} else {
nstate := int32(clr*64000 + clc*1600 + nyr*40 + nyc)
ncost := u.cost + 1
if ncost < dist[nstate] {
dist[nstate] = ncost
prev[nstate] = u.state
action[nstate] = moveChar[i]
heap.Push(Item{state: nstate, cost: ncost})
}
}
}
}
if !found {
fmt.Println("NO")
} else {
fmt.Println("YES")
var path []byte
curr := targetState
for curr != startState {
path = append(path, action[curr])
curr = prev[curr]
}
for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
path[i], path[j] = path[j], path[i]
}
fmt.Println(string(path))
}
}