You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

把一个n行m列的字符阵列看做一个迷宫，迷宫仅包含 “L” , “Q” , “B” , “S” 中的大写字母（蓝桥杯赛的汉语拼音首字母）。

初始时，你可以从任意一个 “L” 字母开始，移向相邻的 “Q” 字母，然后从此 “Q” 字母出发，移向相邻的 “B” 字母，然后从此 “B” 字母出发，移向相邻的 “S” 字母······。这样，你就算是走过了一个 “LQBS” 字符序列。

接下来，仍然可以从此 “S” 字母出发，移向相邻的 “L” 字母······。重复上述的动作，你就可以不断地走过 “LQBS” 序列。 请注意，所谓相邻仅包含上、下、左、右4个方向，且只能从 L → Q ，从 Q→B ，从 B→S ，从 S→L 。

可以想象，由于选择的出发点不同，我们有可能在迷宫中走过无数次的 “LQBS” ，或者是有限次的 “LQBS” ，或者一次也走不了。

请你编写程序，求出在给定的迷宫中，我们最多可以走过多少次 “LQBS” ？

输入格式

第一行：正整数n,m(0 < n , m < 100) ，表示迷宫的规模为n行m列。

接下来的n行：每行m个符合题意的字母，字母间无空格。

输出格式

输出一个整数。即：如果在迷宫中可以无限次地走过 “LQBS” ，则输出 -1 ，否则，输出可以走过 “LQBS” 的最多次数。

样例

1 2
LQ

0

4 4
BLQB
BBQS
SBQL
QQQQ

2