Description

你负责 ICPC（计算机程序评论研究所）的安全工作。该研究所是一栋单层建筑。其矩形楼层被划分成网格状的相同大小的方形区域。如果两个区域共享一条边，则称它们相邻。建筑中的某些区域被阻塞。阻塞区域的所有边都被墙封住，无法进入。所有其他区域之间没有墙壁隔开，相邻区域通常可以互通。然而，在某些相邻区域之间安装了卷帘门，关闭这样的卷帘门会使两个区域之间无法直接移动。

一项绝密研究正在建筑最外侧的某个区域进行。该区域称为绝密区域。建筑只有一个入口，位于最外侧的某个区域，这应该是进入建筑的唯一通道。然而，你发现最外侧某个区域的窗户非常脆弱，可能会让入侵者进入建筑。

你必须保护绝密信息不被入侵者获取。为此，你可能需要关闭一些卷帘门，使得从脆弱窗户所在的区域到绝密区域的路径上需要破坏两个或更多已关闭的卷帘门才能通行。此外，必须存在至少一条从入口区域到绝密区域的路径，且该路径上没有关闭的卷帘门。

你需要编写一个程序，找出保护绝密信息所需关闭的最少卷帘门数量。

Input Format

输入由单个测试用例组成，格式如下。

$$\begin{aligned} &n\ m \\ &s_1 \\ &\vdots \\ &s_n \\ &k \\ &r_1\ c_1\ d_1 \\ &\vdots \\ &r_k\ c_k\ d_k \\ \end{aligned}$$

$n$ 和 $m$ 是介于 $2$ 到 $100$ 之间（含）的整数，表示建筑楼层有 $n$ 行和 $m$ 列区域。第 $i$ 行第 $j$ 列的区域标识为区域 $(i,j)$。接下来的 $n$ 行中，第 $i$ 行有一个长度为 $m$ 的字符串 $s_i$，描述第 $i$ 行的区域。$s_i$ 的每个字符是 .、#、S、T 或 U 之一。如果 $s_i$ 的第 $j$ 个字符是 #，则区域 $(i,j)$ 被阻塞且不可通行；否则，该区域可通行。$s_i$ 的第 $j$ 个字符为 S 表示区域 $(i,j)$ 是入口区域，T 表示绝密区域，U 表示入侵者可能的进入点，即具有脆弱窗户的区域。S、T 和 U 各自在输入中恰好出现一次，且均位于最外侧区域。在卷帘门全部打开的情况下，从入口可通过可通行区域到达绝密区域。

$k$ 是建筑中卷帘门的数量。接下来的 $k$ 行中，第 $i$ 行用两个整数 $r_i$ 和 $c_i$ 以及一个字符 $d_i$ 描述一个卷帘门。$d_i$ 是 r 或 b。如果 $d_i$ 是 r，则满足 $1 \leq r_i \leq n$ 和 $1 \leq c_i < m$，并且卷帘门安装在区域 $(r_i, c_i)$ 和 $(r_i, c_i + 1)$ 之间。如果 $d_i$ 是 b，则满足 $1 \leq r_i < n$ 和 $1 \leq c_i \leq m$，并且卷帘门安装在区域 $(r_i, c_i)$ 和 $(r_i + 1, c_i)$ 之间。相同的 $r_i$、$c_i$ 和 $d_i$ 组合不会出现多次。

Output Format

在一行中输出一个整数，表示保护绝密信息所需关闭的最少卷帘门数量。如果不可能，则输出 $-1$。如果所有卷帘门打开时入侵者也无法到达绝密区域，则输出 $0$。

3 3
S..
#..
U.T
7
1 2 b
1 3 b
2 2 b
2 2 r
2 3 b
3 1 r
3 2 r

3

2 2
ST
.U
4
1 1 r
1 1 b
1 2 b
2 1 r

-1

7 10
U.........
..........
###.......
..........
.......###
..........
S........T
18
4 4 r
5 4 r
6 7 r
7 7 r
3 4 b
3 5 b
3 6 b
3 7 b
3 8 b
3 9 b
3 10 b
5 1 b
5 2 b
5 3 b
5 4 b
5 5 b
5 6 b
5 7 b

14

Hint

样例输入 1 如下图所示。虚线表示卷帘门安装的位置。

:::align{center}

图 C.1. 样例输入 1 :::