بازی TWIN یک بازی یک‌نفره است و روی یک گراف جهت‌دار انجام می‌شود. این گراف $N$ راس دارد. رئوس و یال‌های این گراف با رنگ‌های ۱ تا $N$ رنگ‌آمیزی شده‌اند، در ضمن رنگ هیچ دو راسی یکسان نیست. در ابتدا دو مهره در دو راس $I$ و $W$ قرار دارند و هدف رساندن یکی از این دو مهره در کوتاه‌ترین زمان به خانه‌ی $T$ با توجه به قوانین زیر است:

1. در هر مرحله یکی از دو مهره را (نه لزوما به ترتیب) باید حرکت داد.
2. هر حرکت روی یک یال و در جهت آن انجام می‌شود.
3. یال مورد استفاده در یک مرحله باید هم‌رنگ راس ثابت در آن مرحله باشد.
4. هیچ‌گاه دو مهره در یک راس قرار نمی‌گیرند.

در سطر اول فایل ورودی به ترتیب اعداد $N$، $I$، $W$ و $T$ آمده است $(N\leq 100)$ و پس از آن در $N$ سطر ماتریس مجاورت گراف با توجه به رنگ یال‌ها قرار دارد. توجه داشته باشید که صفر نشانه‌ی عدم وجود یال و عدد غیر صفر رنگ یک یال را مشخص می‌کند. (فرض کنید راس شماره‌ی $v$ رنگ $v$ دارد.)

در سطر اول فایل خروجی تعداد مراحل و در سطرهای بعدی حرکت هر مرحله را بنویسید. یک حرکت به صورت یک زوج $(a,b)$ مشخص می‌شود که $a$ شماره‌ی راس مبدا و $b$ شماره‌ی راس مقصد است. به یاد داشته باشید که هدف کمینه کردن تعداد حرکت‌هاست و فرض کنید ورودی همواره جواب دارد.

• سوال بعد
• سوال قبل