المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۳:سوال ۴

ترتیب نشستن

$N$ نفر به شماره‌های ۱ تا $N$ می‌خواهند با رعایت قواعد زیر کنار هم در یک ردیف بنشینند $(N\leq 50)$. این قواعد به این صورت است: $M$ سه تایی که از ورودی خوانده می‌شود تعیین کننده‌ی قواعد کنار هم نشستن این افراد است. سه تایی $(i,j,k)$ نشان‌دهنده‌ی این است که فرد شماره‌ی $j$ باید بین دو نفر $i$ و $k$ بنشیند. یعنی یکی از دو نفر $i$ و $k$ در سمت راست و دیگری در سمت چپ $j$ بنشیند. ($i$، $j$ و $k$ اعدادی طبیعی و متمایز و کم‌تر یا مساوی $N$ هستند و $M\leq 50$.)

برنامه‌ای بنویسید که با دریافت $M$ و $N$ و این سه تایی‌ها، ترتیبی برای نشستن این افراد در کنار هم با رعایت قواعد داده شده پیدا نماید.

ورودي

در سطر اول فایل ورودی به ترتیب اعداد $N$ و $M$ و در $M$‌سطر بعدی سه‌تایی‌های مذکور نوشته شده‌اند.

خروجي

در فایل خروجی ترتیبی قابل قبول برای نشستن افراد نوشته می‌شود. در صورتی که مسئله جواب ندارد، پیغام NO SOLUTION را در این فایل چاپ کنید.

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
15 10
6 11 12
1 6 14
15 13 3
4 7 10
6 5 8
2 4 9
7 1 13
14 4 11
10 13 8
2 4 7
‎14 6 2 4 7 10 11 15 1 5 9 13 8 3 12‎

ابزار صفحه