Denne oppgaven skulle ha vært Juans historietime om IOI i Sør-Afrika i 1997. Timen ble imidlertid sensurert av resten av komiteen, og dermed har følgende oppgavetekst nådd frem til deg:

Abraham er en modig oppdagelsesreisende som drar dit ingen programmerer har vært før. På sin neste ekspedisjon planlegger han å undersøke en svært merkelig labyrint. Han vet at labyrinten er et rutenett på $n \times n$ med en pil i hver rute. Hver pil peker i én av fire mulige retninger: opp, ned, til venstre eller til høyre. Hvis Abraham trår inn i en rute, er han nødt til å følge pilene fra denne ruten. Hver pil flytter Abraham én rute i retningen den peker; hvis han kommer til en pil som peker ut av labyrinten, kan han unnslippe.

Abraham vet ikke hvilken retning pilene i labyrinten peker i, men han har andre opplysninger. På kartet hans over labyrinten er noen ruter farget svarte og andre hvite. Han tror at hvis han starter i en hvilken som helst svart rute, kan han aldri unnslippe labyrinten, mens han til slutt vil unnslippe hvis han starter i en hvilken som helst hvit rute.

Abrahams antakelse kan være feil: det finnes oppstillinger av svarte og hvite ruter der de angitte betingelsene ikke kan gjelde for alle rutene samtidig, uansett hvilken retning pilene peker i. Bildet nedenfor viser et eksempel.

Kartet representerer en labyrint der de hvite rutene kan oppfylle Abrahams antakelse. Hvis han starter i en av dem, fører de viste pilene ham ut av labyrinten, men det er umulig for ham å forbli fanget når han starter i en svart rute, uansett hvilken retning vi gir pilene som ikke er vist.

Abraham ber deg hjelpe ham med å avgjøre om det, for en gitt fargelegging av rutene på kartet hans, finnes en oppstilling av piler som stemmer med hans oppfatning for hver rute i rutenettet, både svarte og hvite.

Inndata

• Den første linjen inneholder et positivt heltall $n$.
• Hver av de neste $n$ linjene inneholder $n$ tegn, som alle er enten 0 eller 1. 0 betegner en svart rute og 1 en hvit rute. Disse $n$ linjene beskriver rutenettet.

Utdata

Skriv ut SI hvis pilene kan rettes slik at Abraham aldri kan unnslippe når han starter i en svart rute, og til slutt unnslipper når han starter i en hvit rute.

Skriv ut NO hvis dette er umulig.

Eksempler

Inndata 1

3
001
001
111

Utdata 1

SI

Inndata 2

2
01
10

Utdata 2

NO

Merknad

Det første eksemplet svarer til følgende fargelegging (vist til venstre), sammen med en mulig oppstilling av pilretninger:

Det andre eksemplet ble omtalt i oppgavens historie som et tilfelle der de ønskede betingelsene ikke kan oppfylles for alle rutene samtidig.

Begrensninger

• $2 \le n \le 1000$.

Deloppgaver

• Deloppgave 1 (10 poeng): $n=2$.
• Deloppgave 2 (25 poeng): Det er garantert at de svarte rutene danner et sammenhengende område, og minst to av labyrintens hjørner er svarte.
• Deloppgave 3 (25 poeng): Det er garantert at de hvite rutene danner et sammenhengende område, og færre enn $4n-4$ ruter er svarte.
• Deloppgave 4 (40 poeng): Ingen ytterligere begrensninger.

Merknad

En mengde ruter danner et sammenhengende område hvis det finnes en sti mellom hvert par av rutene, med forflytning mellom ruter som deler en kant, som bare går gjennom ruter i mengden. Spesielt danner de svarte rutene et sammenhengende område hvis det finnes en sti som bare består av svarte ruter, mellom hvert par av svarte ruter. Tilsvarende danner de hvite rutene et sammenhengende område hvis det finnes en sti som bare består av hvite ruter, mellom hvert par av hvite ruter.

I det første eksemplet danner både de hvite rutene og de svarte rutene et sammenhengende område.

I det andre eksemplet danner ikke de svarte rutene et sammenhengende område, fordi enhver sti mellom dem også går gjennom en hvit rute.