To zadanie miało być lekcją historii Juana o IOI 1997 w Republice Południowej Afryki. Jednak pozostali członkowie komitetu ocenzurowali tę lekcję, więc dotarła do ciebie następująca treść:

Abraham jest odważnym odkrywcą, który zapuszcza się tam, gdzie nie dotarł jeszcze żaden programista. Podczas następnej wyprawy zamierza zbadać bardzo osobliwy labirynt. Wie, że labirynt jest siatką $n \times n$ ze strzałką w każdym polu. Każda strzałka wskazuje jeden z czterech możliwych kierunków: w górę, w dół, w lewo lub w prawo. Jeśli Abraham wejdzie na pole, musi podążać za strzałkami, zaczynając od tego pola. Każda strzałka przesuwa Abrahama o jedno pole we wskazanym kierunku; jeśli dotrze do strzałki prowadzącej poza labirynt, może uciec.

Abraham nie wie, w którą stronę skierowane są strzałki w labiryncie, ale ma inne informacje. Na jego mapie labiryntu niektóre pola są czarne, a inne białe. Uważa, że jeśli zacznie na dowolnym czarnym polu, nigdy nie zdoła uciec z labiryntu, natomiast jeśli zacznie na dowolnym białym polu, w końcu ucieknie.

Przypuszczenie Abrahama może być błędne: istnieją układy czarnych i białych pól, dla których podane warunki nie mogą zachodzić jednocześnie dla wszystkich pól, niezależnie od kierunków strzałek. Poniższy rysunek przedstawia przykład.

Mapa przedstawia labirynt, w którym białe pola mogą spełniać przypuszczenie Abrahama. Jeśli zacznie na którymkolwiek z nich, pokazane strzałki wyprowadzą go z labiryntu, ale nie może pozostać uwięziony, zaczynając na czarnym polu, niezależnie od tego, jak skierujemy niepokazane strzałki.

Abraham prosi cię o pomoc w ustaleniu, czy dla danego pokolorowania pól na jego mapie istnieje układ strzałek zgodny z jego przekonaniem dla każdego pola siatki, zarówno czarnego, jak i białego.

Wejście

• Pierwszy wiersz zawiera dodatnią liczbę całkowitą $n$.
• Każdy z kolejnych $n$ wierszy zawiera $n$ znaków, z których każdy to 0 lub 1. 0 oznacza czarne pole, a 1 białe pole. Te $n$ wierszy opisuje siatkę.

Wyjście

Wypisz SI, jeśli można skierować strzałki tak, aby Abraham nigdy nie mógł uciec, zaczynając na czarnym polu, i w końcu uciekał, zaczynając na białym polu.

Wypisz NO, jeśli jest to niemożliwe.

Przykład

Wejście 1

3
001
001
111

Wyjście 1

SI

Wejście 2

2
01
10

Wyjście 2

NO

Uwagi

Pierwszemu przykładowi odpowiada następujące pokolorowanie (pokazane po lewej) wraz z możliwym układem kierunków strzałek:

Drugi przykład został wspomniany w opowieści w treści zadania jako przypadek, w którym wymagane warunki nie mogą być spełnione jednocześnie dla wszystkich pól.

Ograniczenia

• $2 \le n \le 1000$.

Podzadania

• Podzadanie 1 (10 punktów): $n=2$.
• Podzadanie 2 (25 punktów): Zagwarantowano, że czarne pola tworzą spójny obszar, a co najmniej dwa narożniki labiryntu są czarne.
• Podzadanie 3 (25 punktów): Zagwarantowano, że białe pola tworzą spójny obszar, a liczba czarnych pól jest mniejsza niż $4n-4$.
• Podzadanie 4 (40 punktów): Bez dodatkowych ograniczeń.

Uwagi

Zbiór pól tworzy spójny obszar, jeśli między każdą parą jego pól istnieje ścieżka przechodząca wyłącznie przez pola tego zbioru, w której przechodzimy między polami mającymi wspólną krawędź. W szczególności czarne pola tworzą spójny obszar, jeśli między każdą parą czarnych pól istnieje ścieżka złożona wyłącznie z czarnych pól. Podobnie białe pola tworzą spójny obszar, jeśli między każdą parą białych pól istnieje ścieżka złożona wyłącznie z białych pól.

W pierwszym przykładzie zarówno białe pola, jak i czarne pola tworzą spójny obszar.

W drugim przykładzie czarne pola nie tworzą spójnego obszaru, ponieważ każda ścieżka między nimi przechodzi również przez białe pole.