金融分析师伊戈尔被闹钟吵醒,赶紧开始工作。他吃完早餐,坐进车里。遗憾的是,当他打开GPS导航仪时,发现自己居住的城市Bankopolis的部分道路因道路施工而封闭。此外,伊戈尔的方向盘有些问题,所以他在去银行办公室的路上最多只能转两圈。
Bankopolis 看起来像一个 n 行 m 列的网格。伊戈尔应该找到一条从家到银行的路,转弯不超过两个,并且不包含道路施工的单元格,或者确定这是不可能的,他应该在家工作。转弯是运动方向的改变。伊戈尔的车只能向左、向右、向上和向下移动。最初伊戈尔可以选择任何方向。伊戈尔还很困,所以你应该帮助他。
输入
第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 1000) — 网格中的行数和列数。
接下来的 n 行中的每一行都包含 m 个字符,表示网格的相应行。可能出现以下字符:
- “。” — 一个空单元格;
- “*” — 有道路工程的单元格;
- “S” — Igor 家所在的小区;
- “T” — Igor 办公室所在的牢房。
保证“S”和“T”各恰好出现一次。
输出
如果 Igor 的家和 Igor 的办公室之间有不超过两圈的路径,则在唯一的行中打印“YES”,否则打印“NO”。
示例
输入 #1
5 5 ..S.. ****. T.... ****. .....
输出 #1
YES
输入 #2
5 5 S.... ****. ..... .**** ..T..
输出 #2
NO
注意
第一个示例如下图所示:
在第二个示例中,不可能使用少于 4 个转弯到达 Igor 的办公室,因此不存在使用不超过 2 个转弯的路径。恰好使用 4 个转弯的路径如下图所示: