도움닫기

세로로 $N$칸, 가로로 $M$칸 크기의 격자가 주어진다. 격자의 각 칸은 빈 칸 또는 함정이다. 이 격자에서 점프는 도움닫기와 멀리뛰기를 차례로 하는 것으로 이루어진다.

1. (도움닫기) 1 이상의 정수 $x$를 고른 뒤, 현재 칸에서 상하좌우 중 한 방향을 골라 1칸씩 $x$번 이동한다. 이동하는 동안 함정이 있는 칸으로 가거나 격자 밖으로 나가서는 안 된다.
2. (멀리뛰기) 이어서 0 이상 $x + 1$ 이하의 정수 $y$를 고른 뒤, 같은 방향으로 $y$칸만큼 뛰어 이동한다. 도착한 칸에 함정이 있거나 격자 밖으로 나가서는 안 된다.

격자의 시작 빈 칸에서 출발해 점프를 임의의 횟수만큼 반복해서 끝 빈 칸에 도착할 수 있는지 판별하라.

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 10\,000$)

이후 $T$개의 테스트 케이스가 주어지며, 각 테스트 케이스는 다음과 같은 형태이다.

첫 번째 줄에 정수 $N$, $M$이 차례대로 주어진다. ($1 \le N, M \le 2\,000$)

두 번째 줄부터 $N$개의 줄에 걸쳐 격자의 각 행을 나타내는 길이 $M$의 문자열이 주어진다. 각 문자는 ., #, S, E 중 하나이며, 의미는 다음과 같다.

• .: 빈 칸
• #: 함정
• S: 시작 빈 칸
• E: 끝 빈 칸

각 테스트 케이스의 격자에는 S와 E가 정확히 하나씩 있다.

모든 테스트 케이스의 $N \times M$의 합은 $4\,000\,000$ 이하이다.

각 테스트 케이스에 대해 한 줄씩 출력한다. E가 적힌 빈 칸에 도달할 수 있으면 YES를, 도달할 수 없으면 NO를 출력한다.