這道題目原本會是 Juan 關於 1997 年南非 IOI 的歷史課。然而，其他委員會成員刪掉了這堂課的內容，因此你現在看到的是以下題目敘述：

Abraham 是一位勇敢的探險家，會前往從未有程式設計師到過的地方。在下一次探險中，他打算探索一座非常奇特的迷宮。他知道迷宮是一個 $n \times n$ 的方格，每個格子中都有一個箭頭。每個箭頭指向四種可能方向之一：上、下、左或右。若 Abraham 踏入某個格子，他就必須從該格開始沿著箭頭前進。每個箭頭會讓 Abraham 朝它所指的方向移動一格；若他走到一個指向迷宮外的箭頭，就能逃出迷宮。

Abraham 不知道迷宮裡的箭頭朝向，但他有其他資訊。在他的迷宮地圖中，有些格子塗成黑色，有些塗成白色。他認為，若從任意黑色格子出發，就永遠無法逃出迷宮；若從任意白色格子出發，則最終都能逃出迷宮。

Abraham 的假設可能是錯的：某些黑白格子的配置，無論如何安排箭頭方向，都無法讓所有格子同時滿足指定條件。下圖展示了一個例子。

這張地圖所代表的迷宮中，白色格子可以滿足 Abraham 的假設。若他從其中任一個白色格子出發，圖示的箭頭都會引導他離開迷宮；但無論如何安排未畫出的箭頭，都不可能讓他從黑色格子出發時一直受困。

Abraham 請你幫他判斷：給定地圖上格子的塗色方式，是否存在一種箭頭配置，能讓方格中的每個格子，不論黑色或白色，都符合他的想法。

輸入格式

• 第一行包含一個正整數 $n$。
• 接下來的 $n$ 行，每行包含 $n$ 個字元，每個字元為 0 或 1。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 分）：無額外限制。

說明

若一組格子中的任意兩個格子之間，都存在一條只經過這組格子、每一步移動到共邊相鄰格子的路徑，則這組格子形成一個連通區域。特別地，若任意兩個黑色格子之間都存在一條只由黑色格子組成的路徑，黑色格子就形成一個連通區域。同樣地，若任意兩個白色格子之間都存在一條只由白色格子組成的路徑，白色格子就形成一個連通區域。

在第一個範例中，白色格子和黑色格子各自都形成一個連通區域。

在第二個範例中，黑色格子沒有形成一個連通區域，因為它們之間的任何路徑都會經過白色格子。