Denna uppgift skulle ha varit Juans historielektion om IOI 1997 i Sydafrika. Lektionen censurerades dock av resten av kommittén, och därför har följande uppgiftsbeskrivning nått dig:

Abraham är en modig upptäcktsresande som går dit ingen programmerare tidigare har gått. På sin nästa expedition tänker han undersöka en mycket märklig labyrint. Han vet att labyrinten är ett rutnät av storlek $n \times n$ med en pil i varje ruta. Varje pil pekar i en av fyra möjliga riktningar: uppåt, nedåt, åt vänster eller åt höger. Om Abraham kliver in i en ruta tvingas han följa pilarna med början i den rutan. Varje pil flyttar Abraham en ruta i den riktning den pekar; om han når en pil som pekar ut ur labyrinten kan han ta sig ut.

Abraham vet inte hur labyrintens pilar är riktade, men han har annan information. På hans karta över labyrinten är vissa rutor svarta och andra vita. Han tror att om han börjar i vilken svart ruta som helst kan han aldrig ta sig ut ur labyrinten, medan han till slut tar sig ut om han börjar i vilken vit ruta som helst.

Abrahams antagande kan vara fel: det finns arrangemang av svarta och vita rutor där de angivna villkoren inte kan gälla för alla rutor samtidigt, oavsett hur pilarna riktas. Följande bild visar ett exempel.

Kartan representerar en labyrint där de vita rutorna kan uppfylla Abrahams antagande. Om han börjar i någon av dem leder de visade pilarna honom ut ur labyrinten, men det är omöjligt för honom att förbli instängd om han börjar i en svart ruta, oavsett hur vi riktar de pilar som inte visas.

Abraham ber dig hjälpa honom att avgöra om det, för en given färgläggning av rutorna på hans karta, finns ett arrangemang av pilar som stämmer överens med hans uppfattning för varje ruta i rutnätet, både svarta och vita.

Indata

• Den första raden innehåller ett positivt heltal $n$.
• Var och en av de följande $n$ raderna innehåller $n$ tecken, vart och ett antingen 0 eller 1. 0 betecknar en svart ruta och 1 en vit ruta. Dessa $n$ rader beskriver rutnätet.

Utdata

Skriv ut SI om pilarna kan riktas så att Abraham aldrig kan ta sig ut om han börjar i en svart ruta, och till slut tar sig ut om han börjar i en vit ruta.

Skriv ut NO om detta är omöjligt.

Exempel

Indata 1

3
001
001
111

Utdata 1

SI

Indata 2

2
01
10

Utdata 2

NO

Förklaring

Det första exemplet motsvarar följande färgläggning (visad till vänster), tillsammans med ett möjligt arrangemang av pilarnas riktningar:

Det andra exemplet nämndes i uppgiftens berättelse som ett fall där de efterfrågade villkoren inte kan uppfyllas för alla rutor samtidigt.

Begränsningar

• $2 \le n \le 1000$.

Deluppgifter

• Deluppgift 1 (10 poäng): $n=2$.
• Deluppgift 2 (25 poäng): De svarta rutorna garanteras bilda ett sammanhängande område, och minst två av labyrintens hörn är svarta.
• Deluppgift 3 (25 poäng): De vita rutorna garanteras bilda ett sammanhängande område, och färre än $4n-4$ rutor är svarta.
• Deluppgift 4 (40 poäng): Inga ytterligare begränsningar.

Förklaring

En mängd rutor bildar ett sammanhängande område om det mellan varje par av dess rutor finns en väg som går mellan rutor som delar en kant och endast passerar genom rutor i mängden. I synnerhet bildar de svarta rutorna ett sammanhängande område om det finns en väg som enbart består av svarta rutor mellan varje par av svarta rutor. På samma sätt bildar de vita rutorna ett sammanhängande område om det finns en väg som enbart består av vita rutor mellan varje par av vita rutor.

I det första exemplet bildar såväl de vita rutorna som de svarta rutorna ett sammanhängande område.

I det andra exemplet bildar de svarta rutorna inte ett sammanhängande område, eftersom varje väg mellan dem också passerar genom en vit ruta.