Woken up by the alarm clock Igor the financial analyst hurried up to the work. He ate his breakfast and sat in his car. Sadly, when he opened his GPS navigator, he found that some of the roads in Bankopolis, the city where he lives, are closed due to road works. Moreover, Igor has some problems with the steering wheel, so he can make no more than two turns on his way to his office in bank.

Bankopolis looks like a grid of *n* rows and *m* columns. Igor should find a way from his home to the bank that has no more than two turns and doesn't contain cells with road works, or determine that it is impossible and he should work from home. A turn is a change in movement direction. Igor's car can only move to the left, to the right, upwards and downwards. Initially Igor can choose any direction. Igor is still sleepy, so you should help him.
The first line contains two integers *n* and *m* (1 ≤ *n*, *m* ≤ 1000) — the number of rows and the number of columns in the grid.

Each of the next *n* lines contains *m* characters denoting the corresponding row of the grid. The following characters can occur: 
 -  "." — an empty cell; -  "*" — a cell with road works; -  "S" — the cell where Igor's home is located; -  "T" — the cell where Igor's office is located. 
It is guaranteed that "S" and "T" appear exactly once each.
The first sample is shown on the following picture:

In the second sample it is impossible to reach Igor's office using less that 4 turns, thus there exists no path using no more than 2 turns. The path using exactly 4 turns is shown on this picture:
5 5
S....
****.
.....
.****
..T..
NO
1 2
ST
YES
3 1
S
*
T
NO
3 3
*..
...
TS.
YES
3 3
T.*
*.*
*S*
YES
7 7
.S.****
...*.*.
.****..
.*.**.*
..T*...
***..*.
*******
YES
3 3
**T
*S*
***
NO
2 2
ST
*.
YES
2 2
S.
.T
YES
2 2
TS
.*
YES
2 2
.T
S*
YES
ipatovi
#8560

lyaguskin — 01.08.2022 21:50
ага, спать
a?kulakov2000 — 01.08.2022 21:52
бляяяя
lyaguskin — 01.08.2022 21:52
че
a?kulakov2000 — 01.08.2022 21:52
Изображение
lyaguskin — 01.08.2022 21:52
хаха
a?kulakov2000 — 01.08.2022 21:53
1 мин не хватило
lyaguskin — 01.08.2022 21:53
у меня в зс было такое
a?kulakov2000 — 01.08.2022 21:53
у меня всегда так
a?kulakov2000 — 01.08.2022 22:00
cf predictor
ipatovi — 02.08.2022 16:58
Есть предложения по названию?
Я предлагаю укропский путч
Нет
Это опасно
С вас ваши отчества, и почты
ipatovi — 02.08.2022 17:55
ну
a?kulakov2000 — 02.08.2022 17:55
сори не видел
ща
Олегович
[email protected]
ipatovi — 02.08.2022 17:56
а, ещё школа
Ваня по моему в 9
а Андрей не помню
a?kulakov2000 — 02.08.2022 17:57
школа №146
название можно стандарт с cf
Изображение
я просто из команд скрин сделал
мне кста рейтинг подняли
ipatovi — 02.08.2022 17:58
мне тоже
a?kulakov2000 — 02.08.2022 17:59
до 1522
ipatovi — 02.08.2022 17:59
крут
a?kulakov2000 — 02.08.2022 17:59
успешно порешали
как тебе название
ipatovi — 02.08.2022 18:00
у меня почему то скрин не прогружается 
a?kulakov2000 — 02.08.2022 18:00
ладно странно
ipatovi — 02.08.2022 18:00
напиши так
a?kulakov2000 — 02.08.2022 18:00
ну там дикий восток
ipatovi — 02.08.2022 18:00
ну я ожидал
a?kulakov2000 — 02.08.2022 18:01
ну типо ты с этим названием целый год участвовал в тренях
ipatovi — 02.08.2022 18:02
я просто хотел что то смешное придумать
ну ладно
a?kulakov2000 — 02.08.2022 18:03
ну можно надо у Вани спросить
так уже легендарная команда
ipatovi — 02.08.2022 18:04
ну, вселенского масштаба
a?kulakov2000 — 02.08.2022 18:04
конечно)
a?kulakov2000 — 02.08.2022 18:59
я смог сдать F!!!
ну задача не очень сложная, без алго
только идея и то простая
но некрасивая реализация
if много
lyaguskin — Сегодня, в 16:23
5 5
S
.*T
..
....
.....
5 5
**S**
**.*T
**.*.
...*.
.....
b10044f7e296a89e.txt
1 кб
def rot90(matrix):
    return [col[::-1] for col in zip(*matrix)]


n, m = [int(i) for i in input().split()]
place = []
Раскрыть
2.txt
3 кб
﻿
def rot90(matrix):
    return [col[::-1] for col in zip(*matrix)]


n, m = [int(i) for i in input().split()]
place = []
for i in range(n):
    place.append(input())
a=place
gorez = []
vert = []
start = []
finish = []
for i in range(n):
    gorez_now = []
    now = 0
    for j in range(m):
        gorez_now.append(now)
        if place[i][j] == '*':
            now += 1
        elif place[i][j] == 'S':
            start = [i, j]
        elif place[i][j] == 'T':
            finish = [i, j]
    gorez.append(gorez_now)
for i in range(m):
    vert_now = []
    now = 0
    for j in range(n):
        vert_now.append(now)
        if place[j][i] == '*':
            now += 1
    vert.append(vert_now)
for i in range(m):
    if place[start[0]][i] != '*' and place[finish[0]][i] != '*' and gorez[start[0]][start[1]] - gorez[start[0]][
        i] == 0 and vert[i][start[0]] - vert[i][finish[0]] == 0 and gorez[finish[0]][i] - gorez[finish[0]][
        finish[1]] == 0:
        print('YES')
        exit()
else:
    place=rot90(a)
    gorez = []
    vert = []
    start = []
    finish = []
    for i in range(n):
        gorez_now = []
        now = 0
        for j in range(m):
            gorez_now.append(now)
            if place[i][j] == '*':
                now += 1
            elif place[i][j] == 'S':
                start = [i, j]
            elif place[i][j] == 'T':
                finish = [i, j]
        gorez.append(gorez_now)
    for i in range(m):
        vert_now = []
        now = 0
        for j in range(n):
            vert_now.append(now)
            if place[j][i] == '*':
                now += 1
        vert.append(vert_now)
    for i in range(m):
        if place[start[0]][i] != '*' and place[finish[0]][i] != '*' and gorez[start[0]][start[1]] - gorez[start[0]][
            i] == 0 and vert[i][start[0]] - vert[i][finish[0]] == 0 and gorez[finish[0]][i] - gorez[finish[0]][
            finish[1]] == 0:
            print('YES')
            exit()
print('NO')