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

به تازگی اسنپ کار خود را گسترش داده‌است و علاوه بر ایران به مردم شکرستان هم سرویس می‌دهد. شکرستان به $N$ منطقه تقسیم شده است و هزینه سفر از منطقه $i$ به منطقه $j$ مقدار مشخصی است که آن را با $A_{ij}$ نشان می‌دهیم. (توجه کنید که ممکن است هزینه سفر از $i$ به $j$ با هزینه سفر از $j$ به $i$ متفاوت باشد.)

این ماه اسکندر $M$ سفر با اسنپ انجام داده‌است و حال میخواهد محاسبه کند که در مجموع چقدر هزینه این سفر‌ها شده است.

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

برای فهم بهتر، بخش ورودی و توضیح ورودی‌ نمونه ۱ را بخوانید.

ورودی🔗

ابتدا در یک سطر $N$ و $M$ که به ترتیب نمایانگر تعداد مناطق شکرستان و تعداد سفرهای اسکندر است، به شما داده می‌شود. سپس در $N$ سطر بعدی در هر خط $N$ عدد به شما داده می‌شود که عدد $j$ ام در سطر $i$ ام هزینه سفر از منطقه $i$ به منطقه $j$‌یا $A_{ij}$ است. سپس در $M$ سطر بعدی در هر سطر به شما دو عدد مانند $x_k$ و $y_k$ به شما داده می‌شود که به ترتیب نمایانگر مبدا و مقصد سفر $k$ ام اسکندر است. برای فهم بیشتر حتما توضیح نمونه ۱ را بخوانید. $2 \le N \le 10$ $1 \le M \le 20$ $1 \le A_{ij} \le 1000$ $1 \le x_k , y_k \le N$ $x_k \ne y_k$

خروجی🔗

در یک خط یک عدد چاپ کنید که نشان‌دهنده هزینه کل سفر‌های اسکندر است.

مثال🔗

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

3 3
1 50 66
72 1 12
91 29 1
1 3
2 3
3 1

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

169

توضیح: با توجه به ورودی های سوال اسکندر ۳ سفر انجام داده است که هزینه سفر اول ۶۶ ، هزینه سفر دوم ۱۲ و هزینه سفر سوم ۹۱ شده است و در مجموع ۱۶۹ = ۹۱ + ۱۲ + ۶۶ پرداخت کرده است.

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

4 4
277 30 971 789
65 379 158 855
892 92 267 454
449 293 735 533
2 3
4 3
1 3
2 4

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

2719

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

از آنجایی که پادشاه و وزیر در شکرستان بیکارترین افراد هستند تصمیم می‌گیرند به همراه بهلول دانا بازی انجام دهند.

بازی به این صورت است که ابتدا پادشاه یک معادله به صورت $A + B = C$ انتخاب می‌کند و آن را بدون اینکه بهلول ببیند در کاغذ می‌نویسد و کاغذ را به وزیر می‌دهد. (هر کدام از $A,B,C$ یک عدد حداکثر ۱۰ رقمی، بدون صفر پشت عدد و نا منفی هستند.)

بعد از آن نوبت به وزیر می‌رسد که از بین $A$ و $B$ و $C$ یک عدد را انتخاب کرده، سپس $x$ رقم متوالی از آن عدد انتخاب کرده و بدون اینکه بهلول ببیند به جای آن فقط یک # می‌گذارد. $x$ میتواند حداقل صفر و حداکثر به اندازه طول عدد انتخابی باشد.

حال نوبت به بهلول می‌رسد، بهلول باید بتواند معادله اولیه را حدس بزند.

از آنجایی که پادشاه بی‌سواد است ممکن است از ابتدا معادله را اشتباه نوشته باشد در این صورت بهلول باید بگوید که معادله از ابتدا اشتباه بوده است.

حال ما به شما معادله دست‌کاری شده توسط وزیر را می‌دهیم و شما باید به بهلول کمک کنید تا بدست آورد که به جای # چه ارقامی باید قرار گیرد، یا اینکه بگویید معادله از اول غلط بوده است.

برای فهم بیشتر سوال بخش ورودی و توضیح ورودی ها را بخوانید.

ورودی🔗

در خط اول یک معادله به شکل $A + B = C$ به شما می‌دهیم که دقیقا یکی از اعداد آن حاوی # است. $0 \le A , B , C \le 10^9$

خروجی🔗

اگر به جای #‌ می‌توانستیم عددی قرار دهیم معادله اولیه را چاپ کنید درغیر اینصورت $-1$ چاپ کنید.

مثال🔗

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

10# + 50 = 10052

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

10002 + 50 = 10052

توضیح : از صورت سوال مشخص است که # برابر $002$ بوده است.

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

#2 + 3 = 26

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

-1

توضیح: از انجایی که جمع یکان اعداد ۵ می‌شود، معادله از اول غلط بوده و نمیتوان عددی جای # گذاشت.

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

12 + 13 = #

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

12 + 13 = 25

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

شرکت Snapp جهت گسترش خدماتش به تازگی اولین نمایندگی خود را در شکرستان افتتاح کرده.

از آنجایی که آشنا شدن مردم شکرستان با Snapp جزو اولویت‌های شرکت محسوب می‌شود، شرکت تصمیم می‌گیرد که قرعه‌کشی عظیمی میان تمامی مردم شکرستان برگزار کند.

به دنبال آن از تمامی مردم شکرستان دعوت ‌می‌شود تا در قرعه‌کشی ثبت‌نام کنند. تنها لازمه‌ی شرکت در قرعه کشی این است که شرکت‌کننده‌ها کلمه شانس خود را روی یک کاغذ بنویسند و در جعبه بیاندازند. تا از میان آنها یک کاغذ به قید قرعه بیرون کشیده شود و به فردی که این کلمه را نوشته جایزه تعلق بگیرد.

اما ممکن است یک شرکت‌کننده به جای یک عدد کاغذ(یک کلمه شانس) تعدادی کاغذ(چندین کلمه‌ی شانس) داخل جعبه بیاندازد و بخواهد تقلب کند. نگران نباشید کارشناسان Snapp فرمول پیچیده‌ای برای حذف کردن کاغذهای اضافی دارند، از نظر کارشناسان Snapp هر دو کلمه شانسی که پیشوندی برابر به طول حداقل $p$ و پسوندی برابر به طول حداقل $q$ داشته باشند، توسط یک فرد به داخل جعبه انداخته شده‌اند و از بین این کلمه ها (کلمه هایی که توسط یک نفر نوشته شده‌اند) تنها یک کلمه در جعبه می‌ماند و باقی کلمه ها حذف می‌شوند.

حال ما به شما تمامی کلمه های اولیه داخل جعبه را می‌دهیم و از شما تعداد نهایی کلمه‌های شانس، پس از اعمال فرمول فوق را می‌خواهیم.

تضمین می‌شود که طول هر کلمه شانس از $p$ , $q$ کمتر نیست.

ورودی🔗

در اولین خط ورودی به ترتیب $n$ و $p$ و $q$ به شما داده می‌شود ($n$ برابر تعداد اولیه کلمه‌های شانس داخل جعبه است). در $n$ خط بعدی در هر خط یک کلمه شانس (متشکل از حروف کوچک انگلیسی) به طول حداکثر ۶۰ آمده است.

$1 \le n \le 20\ 000$ $1 \le p , q \le 60$

خروجی🔗

در تنها خط خروجی تعداد کلمه‌های نهایی داخل جعبه (پس از اعمال فرمول کارشناسان) را چاپ کنید.

مثال🔗

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

3 1 1
armin
akbar
baran

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

3

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

6 2 2
khosi
parsa
matin
ali
alli
parisa

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

4

توضیح نمونه ۲🔗

کلمه‌های شانس parsa و parisa توسط یک نفر و کلمه‌های شانس ali و alli هم توسط یک نفر نوشته شده اند در نتیجه بعد از اعمال فرمول ۴ کلمه شانس داریم!!

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

در جلسه‌ای بین هیات مدیره‌ی شرکت اسنپ، مدیران فریاد «ما پویا هستیم» سر دادند و تصمیم گرفتند کسب و کار شرکتشان را گسترش دهند و علاوه بر داخل شهرها، در دریا هم به مشتریانشان خدمت‌رسانی کنند. به همین جهت تعدادی قایق‌ران استخدام کردند تا به رفت و آمد مسافران بین جزایر کمک کنند.

در نگاه اوّل این طرح بسیار خوب به نظر می‌آمد، امّا پس از مدّتی مسافران متوجّه شدند که تمام سیستم‌های مسیریابی موجود برای داخل شهر ساخته شده‌اند و سیستم مناسبی برای یافتن مسیر بهینه در دریا وجود ندارد. افراد تیم فنّی تصمیم گرفتند خودکفا باشند، لذا فریاد «ما می‌توانیم» سر دادند و خود شروع به طرّاحی چنین سیستمی کردند.

امّا آیا واقعا می‌توانستند؟ ما را در ادامه‌ی این سوال همراهی کنید تا پاسخ این پرسش را بیابیم...

دریا به شکل یک مستطیل با $h$ سطر و $w$ ستون است(متشکّل از $h.w$ خانه به شکل مربّع $1\times 1$). هر یک از جزایر نیز زیر مستطیل‌هایی از دریا را اشغال می‌کنند که اضلاعشان موازی اضلاع آن است؛ هم‌چنین هر خانه از دریا یا به طور کامل در یک جزیره قرار دارد یا به طور کامل خارج از آن است.

قایق در هر خانه که باشد، در ثانیه‌ی بعد می‌تواند به یکی از خانه‌های مجاور ضلعی آن خانه برود؛ شاید باورتان نشود ولی حتّی اگر این خانه‌ها در خشکی باشند، قایق‌های اسنپ توانایی حرکت در آن‌ها را دارند. (مدیران هنگام آغاز طرح، فریاد «ما وسایل نقلیه‌ی خاصی داریم» نیز سر داده بودند) مسافران از رفت و آمد درون دریا متنفّر هستند! پس سیستم مسیریابی باید به ازای تعدادی درخواست شامل یک مبدا و مقصد مشخّص، بگوید کم‌ترین تعداد خانه‌های داخل دریا که باید طی شوند تا از آن مبدا به آن مقصد برسیم چند تاست.

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

مبدا و مقصدهای داده شده صرفا خانه‌هایی داخل دریا هستند و ممکن است درون یک جزیره و یا خارج از تمام جزایر باشند.

برای سهولت در ورودی دادن، سطر‌های دریا را از بالا به پایین با ۱ تا $h$ و ستون‌هایش را به ترتیب از چپ به راست با ۱ تا $w$ شماره‌گذاری کرده‌ایم. برای نشان‌دادن خانه‌ی سطر ‌$i$ام و ستون $j$ام، از دوتایی $i j$ استفاده می‌کنیم.

ورودی🔗

در ورودی استاندارد، ابتدا به ترتیب سه عدد $h$ و $w$ و $n$ (تعداد جزایر) داده می‌شود.

در هر یک از $n$ خط بعد چهار عدد داده می‌شود: به ترتیب $x1$ و $y1$ و $x2$ و $y2$ که نمایانگر خانه‌های دو گوشه‌ی مخالف از جزیره‌ی ‌$i$ام هستند.

در خط $n+2$ عدد $q$ داده می‌شود.

در ادامه $q$ خط وجود خواهد داشت که در $i$امین خط از آن‌ها، مشخصات درخواست $i$ام داده می‌شود. مشخصات هر درخواست، شامل مختصات خانه‌ی مبدا و خانه‌ی مقصد با قالب گفته شده خواهد بود، یعنی اعداد $x1$ و $y1$ و $x2$ و $y2$ با همین ترتیب داده می‌شوند؛ $x1 y1$ مختصات مبدا و $x2 y2$ مختصات خانه‌ی مقصد خواهد بود.

$1 \le n \le 100$ $1 \le q \le 200$ $1 \le h, w \le 10^9$

تضمین می‌شود که هر نقطه اگر روی محیط یک جزیره نباشد، داخل حداکثر یک جزیره است.

خروجی🔗

در خروجی باید $q$ خط چاپ کنید. در خط $i$ام جواب درخواست $i$ام را چاپ کنید.

مثال🔗

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

3 3 2
1 1 1 1
3 3 3 3
2
1 3 3 1
1 2 1 3

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

4
2

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

6 5 4
1 2 1 3
3 1 4 2
3 4 5 4
6 2 6 2
5
1 1 6 5
3 2 3 4
3 3 3 4
3 1 4 2
1 5 6 5

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

5
1
1
0
5

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

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

به علی آقا کمک کنید که بداند حداقل جهت چند جاده را باید عوض کند و آن‌ها چه جاده‌هایی هستند.

ورودی🔗

در خط اول دو عدد $n$ و $m$ آمده است و در $m$ خط بعدی مشخصات جاده‌های شکرستان آمده است؛ به گونه‌ای که در خط $i+1$ ام ورودی دو عدد $u_i$ و $v_i$ آمده‌است که نشان می‌دهد جاده‌ی $i$ام از $u_i$ به $v_i$ است. تضمین می‌شود بین هیچ دو تقاطع‌ای بیشتر از یک جاده نیست و علی آقا از شکرستان خوشش می‌آید.

$1 \le n, m \le 1\ 000\ 000$ $1 \le v_i \neq u_i \le n$

خروجی🔗

در خط اول $t$ کمترین تعداد جاده های لازم که علی آقا باید انتخاب کند را چاپ کنید. در خط $t$ خط بعدی شماره جاده‌هایی که علی آقا باید انتخاب کند را به هر ترتیبی چاپ کنید. در صورت وجود چند جواب یکی را به دلخواه چاپ کنید.

مثال🔗

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

2 1
1 2

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

1
1

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

5 7
3 4
2 4
2 3
1 4
1 3
5 3
5 4

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

1
5

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

شرکت $Snapp$ پس از بررسی‌های بسیار تصمیم به برگزاری مسابقه اسنپ چلنج گرفت. با توجه به زمان کمی که برای تبلیغات باقی مانده بود، بلافاصله پارسا تعدادی پوستر مسابقات را درست کرده و برای تبلیغ به دانشگاه خود می‌برد، پوستری که پارسا طراحی کرده‌است به صورت مستطیلی با طول $n$ و عرض $m$ است. او پس از رسیدن به دانشگاه به سمت بُرد اصلی رفته تا یکی از پوسترها را آنجا بچسباند. برد اصلی دانشگاه به صورت مستطیلی با طول $w$ و عرض $h$ است که $k$ پوستر تبلیغاتی بر روی آن قرار دارد. هر پوستر تبلیغاتی به صورت مستطیلی است که قسمتی از برد را اشغال کرده است و اضلاعش موازی محور‌های مختصات است.حال پارسا می‌خواهد طوری پوستر خود را روی برد بچسباند که روی هیچ پوستر دیگری قرار نگیرد، همچنین با توجه به اهمیّت مسابقه، پارسا می‌خواهد پوستر در جایی قرار بگیرد که دیده شود! در واقع برای دیده شدن پوستر پارسا می‌خواهد نقطه وسط پوسترش در نزدیک‌ترین جای ممکن به نقطه‌ی وسط برد باشد(فاصله‌ی ۲ نقطه فاصله‌ی اقلیدسی آن‌هاست). به پارسا کمک کنید تا ببیند آیا راهی برای چسباندن پوستر وجود دارد. دقت کنید ممکن است سایر پوسترها روی یک دیگر قرار داشته باشند، اما پارسا نمی‌خواهد پوسترش با هیچ کدام از پوستر‌های موجود روی برد اشتراک داشته باشد.همچنین پارسا برای خوانده شدن پوستر،آن را به همان صورتی که هست می‌چسباند و به هیچ وجه پوستر را دوران نمی‌دهد.

ورودی🔗

در سطر اول ورودی به ترتیب چهار عدد $w$ و $h$ و $n$ و $m$ و $k$ است که دو عدد اول ابعاد برد دانشگاه و دو عدد بعدی ابعاد پوستر پارسا‌ است، و عدد آخر تعداد پوستر‌های موجود روی برد است. تضمین می‌شود طول و عرض پوستر پارسا و همچنین طول و عرض برد دانشگاه همگی زوج است. منظور از نقطه‌ی وسط یک مستطیل نقطه‌ای است که فاصله‌اش از چهار گوشه مستطیل برابر است. در ‌$k$ سطر بعدی در هر سطر به ترتیب چهار عدد $(x_{1} , y_{1}, x_{2},y_{2})$ می‌آید که دو راس روبه‌روی پوستر های روی برد است. مختصات ها به صورت دکارتی بوده و نقطه‌ی گوشه‌ی پایین سمت چپ برد نقطه‌ی $(0,0)$ است و نقطه‌ی گوشه بالا سمت راست برد نقطه‌‌ی $(w,h)$ است.

$1 \le w, h , m , n \le 1\ 000\ 000\ 000$ $1\le k \le 100\ 000$ $0 \le x_{1} , x_{2} \le w$ $0\le y_{1} , y_{2} \le h$

خروجی🔗

در سطر اول اگر پارسا ‌می‌توانست پوستر را با شرایط گفته شده روی برد بچسباند yes و در غیر این صورت no را چاپ کنید. در صورتی که جواب شما yes بود در سطر بعدی باید مختصات نقطه گوشه چپ پایین پوستر پارسا بر روی برد را چاپ کنید. دقت کنید مکانی که شما برای پوستر پارسا در نظر می‌گیرید باید تمام شرایط گفته شده را داشته باشد یعنی هم باید در دید باشد(به تعریف در دید بودن مراجعه کنید) و هم نباید روی هیچ یک از پوستر‌های روی برد قرار بگیرد. (اگر چند جواب وجود داشت به دلخواه یک جواب را چاپ کنید.)

مثال🔗

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

4 4 2 2 1 
2 0 4 4 

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

yes
0 1 

توضیح نمونه ۱ : پوستر به رنگ آبی پوستری است که پارسا چسبانده، همچنین نقطه سفید، نقطه‌ی وسط بُرد اصلی دانشگاه و نقطه سیاه نقطه‌ی وسط پوستر پارسا می‌باشد. (دقت کنید که در این نمونه انتخاب پارسا یکتا است و نمی‌تواند جای دیگری را برای پوسترش انتخاب کند.)

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

8 8 2 4 2
7 6 8 2 
0 0 5 4

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

yes
3 4

توضیح نمونه ۲ : پوستر به رنگ آبی پوستری است که پارسا چسبانده (پارسا در این نمونه ۲ انتخاب دارد که یکی از انتخاب‌ها را در شکل زیر مشاهده می‌کنید)، همچنین نقطه سفید، نقطه‌ی وسط بُرد اصلی دانشگاه و نقطه سیاه نقطه‌ی وسط پوستر پارسا می‌باشد. (دقت کنید که پارسا همیشه پوستر را بدون هیچ دورانی می‌چسباند.)

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

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

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

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

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

ورودی🔗

در خط اول $n$ تعداد تقاطع‌ها و $m$ تعداد جاده‌ها می‌آیند.

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

$1 \leq n,m \leq 300\ 000$

خروجی🔗

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

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

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

مثال🔗

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

5 4
1 2
1 3
1 4
1 5

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

2
1 2
2
3 4

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

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

5 8
1 2
2 3
3 4
4 1
1 5
2 5
3 5
4 5

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

2
1 2
2
6 8