지친 페인트공

Ilad Rodavlas은 평생 페인트공으로 일해 왔지만, 자신의 일에 지치기 시작했다. 그는 위로 칠하고, 아래로 칠하고, 다시 위로 칠한다. 매일 똑같은 일이다.

그러던 어느 날, $N \times N$개의 정사각형으로 나뉜 바닥을 칠하려던 그는 기발한 생각을 떠올린다. ``로봇이 나 대신 모든 일을 해 줄 수 있다면 얼마나 좋을까''라고 그는 외친다. 하지만 이 생각에는 두 가지 문제가 있다. 첫째, 로봇은 직진만 할 수 있으므로 항상 한 행 전체 또는 한 열 전체를 같은 색으로 칠한다. 둘째, Ilad는 프로그래밍을 할 수 없다. 하지만 그는 당신이 뛰어난 프로그래머라는 사실을 알고 있으며, 자신을 도와줄 수 있는지 궁금해한다.

Ilad에게는 바닥이 마지막에 정확히 어떤 모습이어야 하는지 보여 주는 그림이 있다. 처음에는 바닥 전체가 칠해져 있지 않다. 로봇에게 바닥을 어떻게 칠해야 하는지 알려 주는 프로그램을 작성하라. 페인트를 낭비하지 않도록 로봇은 같은 행이나 열을 두 번 이상 칠해서는 안 된다.

채점

당신의 풀이는 각각 일정한 점수가 배정된 여러 테스트 그룹으로 평가된다. 각 테스트 그룹에는 여러 테스트 케이스가 포함된다. 한 테스트 그룹의 점수를 얻으려면 그 테스트 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 점수 | 제한 조건

$1$ |$40$| $N \leq 4$

$2$ |$60$| 추가 제한 조건 없음.

첫째 줄에 로봇이 칠할 바닥의 행과 열의 개수를 나타내는 정수 $1 \leq N \leq 9$이 주어진다. 이후 각각 $N$개의 문자로 이루어진 $N$개의 줄이 주어진다. 칠하지 않은 정사각형은 점(.), 검은색 정사각형은 S, 흰색 정사각형은 V로 나타낸다.

주어진 무늬에 따라 바닥을 칠하는 것은 항상 가능하다. 무늬에는 칠해진 정사각형이 적어도 하나 포함된다.

먼저 로봇이 칠해야 하는 행과 열을 순서대로 나타내는 문자열을 출력한다. 행은 위에서 아래로 숫자 1, 2, $\dots$로 나타내고, 열은 왼쪽에서 오른쪽으로 문자 A, B, $\dots$로 나타낸다.

그런 다음 로봇이 매번 사용해야 하는 색을 나타내는 문자열을 출력한다. 흰색은 문자 V, 검은색은 문자 S로 나타낸다.