测试数据来自 system/1681

背景

"我晕...我刚才以为你们是骗我的呢...这个还真能占岛啊.."

是啊...这个世界上并不是所有的土地都是安静的.......
这些四季都漂浮在海面上的岛屿..也许从地球诞生的那一天开始就没有人类涉足过...

描述

我们用一个m*n的矩阵来描述它的地形...
用0表示岩石.木桩...海岸盐碱地等等障碍物.....、
用1来表示可以耕作的土壤..

然后是x0,y0...是出发地点..你荷着锄头从..这里开始开垦...
不可以碰到石头...也不可以经过已经开垦过的土地..*
不过最后可以在任意一个格子停止...

我们的输出的结果应该最多可以开垦的土地块数...
最好还可以把路径也给打印出来...

格式

输入格式

第一行是两个整数，分别代表m，n（m,n<=5）
以下n行，每行m个字符，用来描述岛屿的特征
其中'0'代表石头，'*'代表开垦过的土地，'S'代表起始位置。
注：小岛左上角的坐标为(1,1)

输出格式

第一行，一个整数max，即从起始点开始最多能开垦的土地的块数。
第二行....没有内容
以下max行，每行以(x,y)的格式，按开垦顺序依次输出要开垦的土地的坐标...
如果有多种线路，输出字典顺序最靠先的一条

样例1

样例输入1

3 3
S11
111
111

样例输出1

9

(1,1)
(1,2)
(1,3)
(2,3)
(2,2)
(2,1)
(3,1)
(3,2)
(3,3)

限制

1s

提示

出发点的土地也是可以开垦的额...
对于100%的数据..m,n小于等于5...
...
如果有多种路径...按道理说..应该任意输出一种都行的...
但那个要写SpecialJudge....但我不会写...所以就麻烦一下输出字典序最小的啦...

（*这里有两种说法了..还有一种说法是..可以经过开垦过的土地..
但是这块开垦过土地就被毁坏掉了....后面这个问题会复杂多少..?.）

"花园里花儿香呀.....laalla.."
"遍地是牛羊> <...."

来源

Usaco Training