동물

$R$개의 행과 $C$개의 열로 이루어진 격자에서, 늑대는 $(1, 1)$ 칸에 서 있고 토끼는 $(R, C)$ 칸에 서 있다. 늑대는 $(R, C)$ 칸으로 이동하려 하고, 토끼는 $(1, 1)$ 칸으로 이동하려 한다. 하지만 문제가 하나 있다. 둘의 경로가 교차하면 늑대가 토끼를 따라가며 쫓을 것이다. 이제 격자의 배치가 주어질 때, 토끼와 늑대의 경로가 서로 교차하지 않도록 둘 모두의 경로를 찾을 수 있는지 알아보자. 시작 칸과 도착 칸($(1, 1)$ 및 $(R, C)$)은 경로의 일부로 세지 않는다.

채점

여러 테스트 그룹으로 해답을 평가하며, 각 그룹에는 일정한 점수가 배정되어 있다. 각 테스트 그룹은 여러 테스트 케이스로 이루어진다. 한 테스트 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 점수 | 제한 조건

$1$ |$9$| 장애물이 없다.

$2$ |$10$| $R \cdot C \leq 10$

$3$ |$20$| $R = 3$

$4$ |$25$| $R \cdot C \leq 1000$, 그리고 늑대는 아래쪽과 오른쪽으로만 이동하고 토끼는 위쪽과 왼쪽으로만 이동하는 해가 존재한다.

$5$ |$36$| 추가 제한 조건이 없다.

일부 예제 케이스는 모든 테스트 케이스 그룹에서 유효하지 않다는 점에 유의한다.

첫째 줄에 두 정수 $R$와 $C$가 주어진다. 모든 테스트 케이스에서 $2 \leq R \cdot C \leq 2 \cdot 10^5$가 성립한다.

이어서 $R \times C$ 격자가 주어진다. 각 칸은 빈칸을 뜻하는 .`'' 또는 장애물을 뜻하는 #`'' 중 하나이다.

(1,1) 칸과 (R,C) 칸은 비어 있음이 보장된다.

문제의 요구 사항을 충족하는 두 경로가 존재하지 않으면 NO를 출력한다.

그렇지 않으면 YES를 한 줄에 출력한다. 그런 다음 토끼의 경로를 K`''로, 늑대의 경로를 V`''로 표시한 격자를 출력한다. 격자를 출력할 때 모든 장애물은 장애물로 남아 있어야 하며, 경로에 속하지 않는 모든 빈칸은 빈칸으로 남아 있어야 한다. 경로는 연속적이어야 한다.

C++을 사용한다면, 올바르게 작동하는 해답에서 Time Limit Exceeded이 발생할 위험을 피하기 위해 endl 대신 '\n'을 사용하는 것이 좋을 수 있다.