הבעיה הזאת הייתה אמורה להיות שיעור ההיסטוריה של Juan על IOI של שנת 1997 בדרום אפריקה. אולם שאר חברי הוועדה צנזרו את השיעור, ולכן הגיע אליכם הנוסח הבא:

Abraham הוא חוקר אמיץ ההולך למקומות שאף מתכנת לא הגיע אליהם לפניו. במשלחת הבאה שלו הוא מתכנן לחקור מבוך מסקרן מאוד. הוא יודע שהמבוך הוא לוח בגודל $n \times n$ עם חץ בכל תא. כל חץ מצביע לאחד מארבעה כיוונים אפשריים: למעלה, למטה, שמאלה או ימינה. אם Abraham דורך בתא, הוא נאלץ לעקוב אחר החצים החל מאותו תא. כל חץ מזיז את Abraham תא אחד בכיוון שאליו הוא מצביע; אם הוא מגיע לחץ המצביע אל מחוץ למבוך, הוא יכול להיחלץ.

Abraham אינו יודע לאילו כיוונים מצביעים חצי המבוך, אך יש לו מידע אחר. במפת המבוך שלו, חלק מהתאים צבועים בשחור ואחרים בלבן. הוא מאמין שאם יתחיל בתא שחור כלשהו, לעולם לא יוכל להיחלץ מהמבוך, ואילו אם יתחיל בתא לבן כלשהו, הוא ייחלץ בסופו של דבר.

ייתכן שההנחה של Abraham שגויה: יש סידורים של תאים שחורים ולבנים שבהם התנאים שצוינו אינם יכולים להתקיים עבור כל התאים בו־זמנית, ללא תלות בכיווני החצים. התמונה הבאה מציגה דוגמה.

המפה מייצגת מבוך שבו התאים הלבנים יכולים לקיים את ההנחה של Abraham. אם יתחיל באחד מהם, החצים המוצגים יובילו אותו אל מחוץ למבוך, אך אין אפשרות שיישאר לכוד כאשר יתחיל בתא שחור, ללא תלות באופן שבו נכוון את החצים שאינם מוצגים.

Abraham מבקש מכם לעזור לו לקבוע אם, עבור צביעה נתונה של התאים במפה שלו, קיים סידור חצים התואם לאמונתו עבור כל תא בלוח, שחור ולבן כאחד.

קלט

• השורה הראשונה מכילה מספר שלם חיובי $n$.
• כל אחת מ־$n$ השורות הבאות מכילה $n$ תווים, שכל אחד מהם הוא 0 או 1. 0 מציין תא שחור ו־1 תא לבן. $n$ השורות האלה מתארות את הלוח.

פלט

הדפיסו SI אם ניתן לכוון את החצים כך ש־Abraham לעולם לא יוכל להיחלץ כאשר הוא מתחיל בתא שחור, וייחלץ בסופו של דבר כאשר הוא מתחיל בתא לבן.

הדפיסו NO אם הדבר בלתי אפשרי.

דוגמאות

קלט 1

3
001
001
111

פלט 1

SI

קלט 2

2
01
10

פלט 2

NO

הערה

הדוגמה הראשונה מתאימה לצביעה הבאה (המוצגת משמאל), יחד עם סידור אפשרי של כיווני החצים:

הדוגמה השנייה הוזכרה בסיפור הבעיה כמקרה שבו אי אפשר לקיים את התנאים המבוקשים עבור כל התאים בו־זמנית.

מגבלות

• $2 \le n \le 1000$.

תתי־משימות

• תת־משימה 1 (10 נקודות): $n=2$.
• תת־משימה 2 (25 נקודות): מובטח שהתאים השחורים יוצרים אזור קשיר, ושלפחות שתיים מפינות המבוך שחורות.
• תת־משימה 3 (25 נקודות): מובטח שהתאים הלבנים יוצרים אזור קשיר, ושפחות מ־$4n-4$ תאים שחורים.
• תת־משימה 4 (40 נקודות): ללא מגבלות נוספות.

הערה

קבוצת תאים יוצרת אזור קשיר אם בין כל זוג תאים שלה יש מסלול, הנע בין תאים החולקים צלע, שעובר רק בתאים של הקבוצה. בפרט, התאים השחורים יוצרים אזור קשיר אם בין כל זוג תאים שחורים יש מסלול המורכב רק מתאים שחורים. באופן דומה, התאים הלבנים יוצרים אזור קשיר אם בין כל זוג תאים לבנים יש מסלול המורכב רק מתאים לבנים.

בדוגמה הראשונה, גם התאים הלבנים וגם התאים השחורים יוצרים אזור קשיר.

בדוגמה השנייה, התאים השחורים אינם יוצרים אזור קשיר משום שכל מסלול ביניהם עובר גם בתא לבן.