题目描述

ACM是一个喜欢玩游戏的小孩，他喜欢玩智力游戏，比如最近在玩走迷宫，
这是一款超级耗费脑细胞的游戏，和普通的走迷宫一样，游戏是一张迷宫图，
其中有一些标记，'W'是墙，'.'是可走的路，有一个'S'和'E'，分别表示起点和目标点。
和普通游戏不一样的是，游戏要你找出所有的通路，并按规则告诉系统。
图中的点在一条通路中最多出现一次。
很有压力吧？那是对于非计算机专业的人来说！你怎么看？试试吧。

输入要求

测试数据为多组输入。
每组数据首先是两个整数n和m（1<n、m<6)

输出要求

每组数据首先一行输出一个整数表示从起点到终点能行的路径数x。
接下来x行，输出这x条路径。
输出规则如下：
路径用行进方向表示，a、b、c、d分别表示上、下、左、右。
多条路径先输出步数少的。
步数一样的先输出路径序列字典序小的。

输入样例

4 5
S.W.W
W....
..WW.
....E

输出样例

3
dbbbddd
dbdddbb
dbbcbdddd

提示

来源

NBU OJ