مضدو


  • محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

در محلّه‌ی «مضدو» در شهر شکرستان مردمی زندگی می‌کنند که عاشق ۲ و اعداد مضرب ۲ هستند؛ این مردم از زمانی که این شهر ایجاد شد بر اریکه‌ی قدرت نشسته اند.

این شهر متشکل از nn تقاطع است. mm جاده‌ی دو طرفه نیز وجود دارد که هر کدام از آن‌ها دو تقاطع را به هم وصل می‌کند. پیرو ارادت اجداد ساکنین مضدو به عدد ۲، در هنگام ساخت شهر، تعداد زوجی جاده ساخته شد. هم‌چنین در شکرستان از هر تقاطعی می‌توان با گذر از تعدادی جاده به هر تقاطع دیگر رفت. وزیر مسکن شکرستان که خود نیز از ساکنین مضدو است، می‌خواهد به هر کسی در شکرستان دو خانه هدیه بدهد.(به راستی که چه وزیر مهربانی...) در تقاطع‌هایی که تعداد جاده‌های متصل به آن‌ها مضرب ۲ نیست، خانه قرار دارد (به راستی چرا؟!) و به آن‌ها گفته است هر کدام از شما باید دو خانه و جاده‌های یک مسیر بین آن‌ها را برای خودتان انتخاب کنید.

مردم شکرستان از روی مهر و عطوفتشان نسبت به عدد ۲، دوست دارند مسیری که بین دو خانه‌شان انتخاب می‌کنند دارای زوج جاده باشد. هم‌چنین دوست ندارند که در این مسیر از یک جاده دو بار رد شوند؛ امّا با این که از یک تقاطع چند بار رد شوند مشکلی ندارند. آن‌ها هم‌چنین بسیار انحصار طلب هستند، به گونه‌ای که اصلا دلشان نمی‌خواهد خانه یا جاده‌ای متعلق به بیش از یک نفر از آن‌ها باشد.

فرض کنید این شهر kk خانه و دقیقاً k2\frac{k}{2} شهروند دارد. تضمین می‌شود kk عددی طبیعی است. به شهروندان در انتخاب کردن خانه‌ها و مسیر بینشان کمک کنید و اگر چنین چیزی ممکن نبود، بگویید که این کار ناممکن است.

ورودی🔗

در خط اول nn تعداد تقاطع‌ها و mm تعداد جاده‌ها می‌آیند.

در خط iiام از mm خط بعدی، دو عدد می‌آیند که اندیس تقاطع‌های دو سر جاده‌ی iiام هستند.

1n,m300 0001 \leq n,m \leq 300\ 000

خروجی🔗

اگر این کار ممکن نیست، در خروجی Impossible چاپ کنید.

در غیر این صورت به ازای هر یک از k2\frac{k}{2} مسیر مطلوب، دو خط باید چاپ کنید. خط اوّل باید شامل یک عدد باشد: تعداد جاده‌های مسیر(که مضربی از ۲ است) در خط دوم نیز باید اندیس جاده‌های آن مسیر را به ترتیب طی شدن چاپ کنید. (با space از هم جدا شوند.)

اگر چند جواب وجود داشت، شما مجازید هر کدام را که می‌خواهید چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

5 4
1 2
1 3
1 4
1 5
Plain text

خروجی نمونه ۱🔗

2
1 2
2
3 4
Plain text

در این نمونه، در تقاطع‌های ۲ و ۳ و ۴ و ۵ خانه وجود دارد که هر کدام با یک جاده به تقاطع ۱ وصل شده اند. جاده‌های ۱ و ۲ بین تقاطع‌های ۲ و ۳ مسیر می‌سازند و جاده‌های ۴ و ۳ نیز بین تقاطع‌های ۴ و ۵.

ورودی نمونه ۲🔗

5 8
1 2
2 3
3 4
4 1
1 5
2 5
3 5
4 5
Plain text

خروجی نمونه ۲🔗

2
1 2
2
6 8
Plain text
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.