+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۶۴ مگابایت ---------- کریم یک کودک ۵ ساله است و در گردهمایی مهدکودکی‌ها شرکت می‌کند. کریم و $n - 1$ نفر از هم مهدی‌هایش دور یک میز دایره‌ای شکل جهت صرف دوغ گرد هم آمده‌اند. آن‌ها را با شروع از کریم و بصورت ساعتگرد، با اعداد 1 تا $n$ شماره‌گذاری می‌کنیم. بین برخی از این کودکان رابطه‌ی دوطرفه‌ی دوستی برقرار است. پس از انتظارهای بسیار، یک عدد پارچ دوغ به کنار میز آورده می‌شود. همه‌ی این $n$ نفر می‌خواهند از این دوغ بنوشند. روند دوغ‌رسانی در این قبیل گردهمایی‌ها به این صورت است که پارچ دوغ ابتدا به یکی از افراد دور میز داده می‌شود. هرکسی که پارچ به دستش میرسد پس از نوشیدن مقداری از آن، پارچ دوغ را به یکی از دوستانش که هنوز دوغ نخورده است می‌دهد تا وقتی که همه از آن بنوشند. دقت کنید که بخاطر سن کم، هیچ کس پارچ دوغ را به کسی که با او دوست نیست نمی‌دهد. به دلیل بزرگ بودن میز و کوچک بودن کودکان، هرکس برای رساندن دوغ به نفر بعدی به روی میز میرود و هنگام راه رفتن روی مسیر بین جایگاه نشستن خود و نفر بعدی، خطی از دوغ روی میز باقی می‌گذارد. روی هیچ نقطه‌ای از مسیری که یک کودک به سمت کودک بعدی طی می‌کند نباید از قبل دوغی ریخته شده باشد؛ چون کودک هنگام حمل دوغ لیز خورده و خاطره‌ی بدی از گردهمایی بجا خواهد ماند. حال با دانستن روابط دوستی بین این کودکان، بگویید که این ها به چه ترتیبی می‌توانند دوغ بخورند که به همه دوغ برسد و هیچکس هنگام حمل دوغ زمین نخورد. (یا بگویید که امکان ندارد.) # ورودی خط اول ورودی شامل عدد $n$ است. در خط دوم ورودی عدد $m$ که بیانگر تعداد رابطه های دوستی بین کودکان است. هریک از $m$ خط بعدی یک جفت عدد $u, v$ آمده که یعنی کودک شماره $u$ و کودک شماره $v$ با هم دوست هستند. $$3 \le n \le 1000$$ $$0 \le m \le \frac{n \times (n-1)}2$$ # خروجی اگر امکان ندارد که به همه با شرایط گفته شده دوغ برسد، تنها خط خروجی باید شامل عدد $-1$ باشد. در غیر این صورت خروجی برنامه باید ترتیبی صحیح از دوغ خوردن افراد باشد که در $n$ خط آمده است. در صورت وجود چند ترتیب درست، یکی را به دلخواه خروجی دهید. # ورودی نمونه ۱ ``` 7 9 1 4 5 1 1 7 5 6 2 3 3 4 2 6 4 6 6 7 ``` # خروجی نمونه ۱ ``` 2 3 4 1 7 6 5 ``` # ورودی نمونه ۲ ``` 4 3 1 2 2 4 1 3 ``` # خروجی نمونه ۲ ``` -1 ```

حل سؤال در بانک سؤالات