Problem description

Istnieje taki edytor tekstu (a może system operacyjny bez edytora tekstu) Emacs. Jako zaawansowane narzędzie do edycji tekstu zawiera w sobie kilka umilaczy. Między innymi grę 5x5. Zasady są proste: mamy dany kwadrat 5 × 5, w którym niektóre pola są zapalone, a niektóre zgaszone. W jednym ruchu możemy wybrać pole i zmienić jego stan (z zapalonego na zgaszony i na odwrót), przy czym zmienia się też stan pola nad nim, pod nim, na lewo od niego oraz na prawo od niego (jeśli takie istnieją). Celem w grze jest zgaszenie wszystkich pól. Rozważmy tę grę nieco ogólniej. Będziemy analizowali grę na tych samych zasadach, lecz plansza może być kwadratem o dowolnym boku długości N, a nie tylko 5.

Napisz program, który: wczyta długość boku kwadratu oraz konfigurację początkową planszy, obliczy minimalną liczbę ruchów niezbędną do zwycięstwa lub stwierdzi, że zwycięstwo jest nieosiągalne, wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca długość boku kwadratowej planszy. W kolejnych N wierszach znajduje się opis kwadratowej planszy. Każdy wiersz zawiera dokładnie N cyfr 0 lub 1, pooddzielanych pojedynczymi odstępami, gdzie 0 oznacza, że dane pole jest zgaszone, natomiast 1 – zapalone.

Wyjście

W pierwszym i jedynym wierszu wyjścia należy wypisać dokładnie jedną liczbę całkowitą – minimalną liczbę ruchów niezbędną do zwycięstwa. Jeśli zwycięstwo jest niemożliwe – należy wypisać NIE.

Ograniczenia

3 ≤ N ≤ 16.

Przykład

3
0 0 1
1 1 0
0 1 0

2