كان من المفترض أن تكون هذه المسألة درس 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 نقطة): لا توجد قيود إضافية.

ملاحظة

تشكل مجموعة من الخلايا منطقة متصلة إذا وُجد بين كل زوج من خلاياها مسار ينتقل بين الخلايا التي تشترك في ضلع، ولا يمر إلا بخلايا المجموعة. على وجه الخصوص، تشكل الخلايا السوداء منطقة متصلة إذا وُجد بين كل زوج من الخلايا السوداء مسار يتكون من خلايا سوداء فقط. وبالمثل، تشكل الخلايا البيضاء منطقة متصلة إذا وُجد بين كل زوج من الخلايا البيضاء مسار يتكون من خلايا بيضاء فقط.

في المثال الأول، تشكل كل من الخلايا البيضاء والخلايا السوداء منطقة متصلة.

في المثال الثاني، لا تشكل الخلايا السوداء منطقة متصلة، لأن أي مسار بينها يمر أيضا بخلية بيضاء.