Tämän tehtävän piti olla Juanin historian oppitunti Etelä-Afrikassa järjestetystä vuoden 1997 IOI:sta. Muu komitea kuitenkin sensuroi oppitunnin, joten olet saanut seuraavan tehtävänannon:

Abraham on rohkea tutkimusmatkailija, joka menee sinne, missä yksikään ohjelmoija ei ole ennen käynyt. Seuraavalla tutkimusretkellään hän aikoo tutkia hyvin erikoista labyrinttia. Hän tietää, että labyrintti on $n \times n$ ruudukko, jonka jokaisessa ruudussa on nuoli. Kukin nuoli osoittaa yhteen neljästä mahdollisesta suunnasta: ylös, alas, vasemmalle tai oikealle. Jos Abraham astuu ruutuun, hänen on pakko seurata nuolia siitä ruudusta lähtien. Jokainen nuoli siirtää Abrahamia yhden ruudun osoittamaansa suuntaan; jos hän saavuttaa labyrintista ulos osoittavan nuolen, hän pääsee pakoon.

Abraham ei tiedä labyrintin nuolten suuntia, mutta hänellä on muita tietoja. Hänen labyrinttikartassaan jotkin ruudut on väritetty mustiksi ja toiset valkoisiksi. Hän uskoo, ettei hän koskaan pääse pois labyrintista aloittaessaan mistä tahansa mustasta ruudusta, kun taas mistä tahansa valkoisesta ruudusta aloittaessaan hän pääsee lopulta pakoon.

Abrahamin oletus voi olla väärä: on olemassa mustien ja valkoisten ruutujen asetelmia, joissa annetut ehdot eivät voi toteutua kaikille ruuduille samanaikaisesti riippumatta nuolten suunnista. Seuraava kuva näyttää esimerkin.

Kartta esittää labyrinttia, jonka valkoiset ruudut voivat täyttää Abrahamin oletuksen. Jos hän aloittaa kummasta tahansa niistä, kuvan nuolet johtavat hänet ulos labyrintista, mutta hänen on mahdotonta jäädä loukkuun mustasta ruudusta aloittaessaan riippumatta siitä, miten suuntaamme nuolet, joita kuvassa ei näytetä.

Abraham pyytää sinua auttamaan selvittämään, onko hänen karttansa ruutujen annetulle väritykselle olemassa nuolten asetelma, joka vastaa hänen uskomustaan ruudukon jokaisen ruudun osalta, sekä mustien että valkoisten.

Syöte

• Ensimmäisellä rivillä on positiivinen kokonaisluku $n$.
• Kullakin seuraavista $n$ rivistä on $n$ merkkiä, joista jokainen on joko 0 tai 1. 0 tarkoittaa mustaa ruutua ja 1 valkoista ruutua. Nämä $n$ riviä kuvaavat ruudukon.

Tuloste

Tulosta SI, jos nuolet voidaan suunnata niin, ettei Abraham koskaan pääse pakoon mustasta ruudusta aloittaessaan ja että hän pääsee lopulta pakoon valkoisesta ruudusta aloittaessaan.

Tulosta NO, jos tämä on mahdotonta.

Esimerkit

Syöte 1

3
001
001
111

Tuloste 1

SI

Syöte 2

2
01
10

Tuloste 2

NO

Selitys

Ensimmäinen esimerkki vastaa seuraavaa väritystä (vasemmalla) sekä yhtä mahdollista nuolten suuntien asetelmaa:

Toinen esimerkki mainittiin tehtävän tarinassa tapauksena, jossa vaadittuja ehtoja ei voida täyttää kaikille ruuduille samanaikaisesti.

Rajat

• $2 \le n \le 1000$.

Osatehtävät

• Osatehtävä 1 (10 pistettä): $n=2$.
• Osatehtävä 2 (25 pistettä): Mustat ruudut muodostavat varmasti yhtenäisen alueen, ja ainakin kaksi labyrintin kulmaa on mustia.
• Osatehtävä 3 (25 pistettä): Valkoiset ruudut muodostavat varmasti yhtenäisen alueen, ja mustia ruutuja on vähemmän kuin $4n-4$.
• Osatehtävä 4 (40 pistettä): Ei lisärajoituksia.

Huomautus

Ruutujoukko muodostaa yhtenäisen alueen, jos sen jokaisen ruutuparin välillä on polku, joka kulkee vain joukon ruutujen kautta ja jossa siirrytään yhteisen sivun jakavien ruutujen välillä. Erityisesti mustat ruudut muodostavat yhtenäisen alueen, jos jokaisen mustan ruutuparin välillä on vain mustista ruuduista koostuva polku. Vastaavasti valkoiset ruudut muodostavat yhtenäisen alueen, jos jokaisen valkoisen ruutuparin välillä on vain valkoisista ruuduista koostuva polku.

Ensimmäisessä esimerkissä sekä valkoiset ruudut että mustat ruudut muodostavat yhtenäisen alueen.

Toisessa esimerkissä mustat ruudut eivät muodosta yhtenäistä aluetta, koska jokainen niiden välinen polku kulkee myös valkoisen ruudun kautta.