33578번 - 누가 이름 안 적고 나갔어

문제

디미고에서는 야간 자율 학습 시간에 교실 밖으로 나가려면 칠판에 이름을 적고 나가야 한다. 하지만 승찬이는 이름을 적지 않고 교실 밖으로 나가곤 한다. 이런 경우 인원 점검을 담당하는 진우는 선생님께 도움을 요청하거나 직접 승찬이를 찾아야 한다. 승찬이와 같은 칸에 있는 경우 승찬이를 찾을 수 있고, 선생님과 같은 칸에 있는 경우 선생님께 도움을 요청할 수 있다. 승찬이는 이동하지 않으며, 선생님은 진우가 도움을 요청하기 전까지 이동하지 않는다.

학교는 $N \times M$ 크기의 격자 형태로 표현할 수 있다. 각 칸은 아래 중 한 문자로 표현할 수 있다.

• S: 승찬이가 있는 칸. 반드시 하나만 존재한다.
• J: 진우가 있는 칸. 반드시 하나만 존재한다.
• T: 선생님이 있는 칸. 0ドル$개 이상 존재한다.
• .: 복도. 진우와 선생님이 자유롭게 이동할 수 있다.
• #: 벽. 진우와 선생님이 지나갈 수 없다.

승찬이, 진우, 선생님이 위치한 칸은 모두 복도에 해당한다. 진우는 2ドル$초에 1ドル$칸씩, 선생님은 1ドル$초에 1ドル$칸씩 상하좌우로 인접한 복도 칸으로 이동할 수 있다. 도움을 요청하는 데 걸리는 시간은 고려하지 않는다.

진우가 승찬이를 찾는 데 걸리는 시간의 최솟값을 구하시오.

입력

첫 번째 줄에 정수 $N$과 $M$이 공백으로 구분하여 주어진다. $(2 \leq N, M \leq 3,000円)$

두 번째 줄부터 $N$개의 줄에 걸쳐 길이 $M$의 문자열이 주어진다. 각 문자열은 학교의 구조를 나타내며, 각각의 문자는 하나의 칸을 의미한다.

선생님이 있는 칸이 없을 수 있음에 유의하라.

출력

첫 번째 줄에 승찬이를 찾는 데 걸리는 시간의 최솟값을 출력한다. 만약 승찬이를 찾을 수 없다면 대신 -1을 출력한다.

제한

힌트