이 문제는 원래 Juan이 남아프리카 공화국에서 열린 1997년 IOI에 대해 들려주는 역사 수업이 될 예정이었다. 그러나 위원회의 다른 구성원들이 그 수업을 검열했고, 그래서 여러분에게는 다음과 같은 지문이 전달되었다.

Abraham은 어떤 프로그래머도 가 본 적 없는 곳으로 향하는 용감한 탐험가이다. 다음 탐험에서 그는 아주 기묘한 미로를 조사할 계획이다. 그는 미로가 각 칸에 화살표가 있는 $n \times n$ 격자라는 것을 알고 있다. 각 화살표는 위, 아래, 왼쪽, 오른쪽의 네 방향 중 하나를 가리킨다. Abraham이 어떤 칸에 들어서면 그 칸부터 화살표를 따라가야 한다. 각 화살표는 Abraham을 가리키는 방향으로 한 칸 이동시킨다. 미로 밖을 가리키는 화살표에 도달하면 탈출할 수 있다.

Abraham은 미로의 화살표가 어느 방향을 향하는지 모르지만, 다른 정보는 가지고 있다. 그의 미로 지도에는 어떤 칸은 검은색으로, 나머지 칸은 흰색으로 칠해져 있다. 그는 어떤 검은 칸에서 출발하든 절대 미로에서 탈출할 수 없고, 어떤 흰 칸에서 출발하든 결국 탈출할 것이라고 믿는다.

Abraham의 추측은 틀릴 수 있다. 화살표를 어느 방향으로 놓더라도 모든 칸이 주어진 조건을 동시에 만족할 수 없는 흑백 칸 배치가 존재한다. 다음 그림은 그러한 예를 보여 준다.

이 지도는 흰 칸들이 Abraham의 추측을 만족할 수 있는 미로를 나타낸다. 두 흰 칸 중 어느 곳에서 출발하든 그림의 화살표를 따라 미로 밖으로 나갈 수 있지만, 표시되지 않은 화살표를 어느 방향으로 놓더라도 검은 칸에서 출발했을 때 갇혀 있도록 만드는 것은 불가능하다.

Abraham은 지도에 있는 칸의 색칠이 주어졌을 때, 검은 칸과 흰 칸을 포함한 격자의 모든 칸에서 자신의 믿음과 일치하는 화살표 배치가 존재하는지 판별하는 것을 도와 달라고 한다.

입력

• 첫 번째 줄에 양의 정수 $n$이 주어진다.
• 다음 $n$개 줄에는 각각 0 또는 1인 문자 $n$개가 주어진다. 0은 검은 칸을, 1은 흰 칸을 나타낸다. 이 $n$개 줄이 격자를 나타낸다.

출력

Abraham이 검은 칸에서 출발하면 절대 탈출할 수 없고 흰 칸에서 출발하면 결국 탈출하도록 화살표의 방향을 정할 수 있으면 SI를 출력한다.

불가능하면 NO를 출력한다.

예제

입력 1

3
001
001
111

출력 1

SI

입력 2

2
01
10

출력 2

NO

참고

첫 번째 예제는 아래의 색칠 (왼쪽 그림)과 이에 대한 가능한 화살표 방향 배치에 해당한다.

두 번째 예제는 모든 칸이 요구되는 조건을 동시에 만족할 수 없는 경우로 문제의 이야기에서 언급되었다.

제한

• $2 \le n \le 1000$.

서브태스크

• 서브태스크 1 (10점): $n=2$.
• 서브태스크 2 (25점): 검은 칸들이 연결된 영역을 이루며, 미로의 모서리 중 적어도 두 곳이 검은색임이 보장된다.
• 서브태스크 3 (25점): 흰 칸들이 연결된 영역을 이루며, 검은 칸의 수는 $4n-4$보다 적음이 보장된다.
• 서브태스크 4 (40점): 추가 제한이 없다.

참고

칸들의 집합에서 임의의 두 칸 사이에, 변을 공유하는 칸 사이로 이동하며 그 집합의 칸만 지나는 경로가 존재하면 그 집합은 연결된 영역을 이룬다. 특히, 임의의 두 검은 칸 사이에 검은 칸만으로 이루어진 경로가 있으면 검은 칸들은 연결된 영역을 이룬다. 마찬가지로 임의의 두 흰 칸 사이에 흰 칸만으로 이루어진 경로가 있으면 흰 칸들은 연결된 영역을 이룬다.

첫 번째 예제에서는 흰 칸들과 검은 칸들이 각각 연결된 영역을 이룬다.

두 번째 예제에서는 검은 칸 사이의 모든 경로가 흰 칸도 지나므로, 검은 칸들은 연결된 영역을 이루지 않는다.