• محدودیت زمان: ۱۰ ثانیه (برای تمامی زبان‌های برنامه‌نویسی)
• محدودیت حافظه: ۵۱۲ مگابایت (برای تمامی زبان‌های برنامه‌نویسی)

---

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

رئوس گراف با اعداد طبیعی از \(1\) تا \(n\) شماره‌گذاری شده‌اند.

ورودی

در اولین خط ورودی دو عدد \(n\) و \(m\) با یک فاصله بینشان آمده‌است که به ترتیب تعداد رئوس و یال‌های گراف را نشان می‌دهد. \[1 \leq n \leq 2000\] \[0 \leq m \leq \frac{n(n - 1)}{2}\]

در ادامه \(m\) خط در ورودی آمده‌است. در \(i\)امین خط از \(m\) خط بعدی، دو عدد طبیعی \(x_i\) و \(y_i\) نابرابر با یک فاصله بینشان آمده‌است که نشان می‌دهد یال \((x_i, y_i)\) در گراف وجود دارد.

به ازای هر \(i\) معتبر داریم: \[ 1 \leq x_i, y_i \leq n \] \[ x_i \neq y_i \]

خروجی

در اولین خط، اول \(a\) (تعداد یال‌های لازم برای حذف شدن از گراف) و سپس \(b\) (تعداد یال‌های لازم برای اضافه شدن به گراف) را با یک فاصله چاپ کنید. در هر یک از \(a\) خط بعدی، شماره‌ی رئوس دو سر هر یالی که لازم است از گراف حذف شود را با یک فاصله چاپ کنید. سپس در هر یک از \(b\) خط بعدی، شماره‌ی رئوس دو سر هر یالی که لازم است به گراف اضافه شود را با یک فاصله چاپ کنید.

مثال

ورودی نمونه ۱

3 2
1 2
2 3

خروجی نمونه ۱

0 0

ورودی نمونه ۲

3 3
1 2
2 3
3 1

خروجی نمونه ۲

1 0
1 3

ورودی نمونه ۳

4 0

خروجی نمونه ۳

0 3
1 2
2 3
3 4

نکات

• هر جواب دلخواهی که گراف ورودی را تبدیل به یک درخت بکند معتبر خواهد بود، ترتیب چاپ کردن یال‌های خروجی مهم نیست، فقط دقت کنید که مقدار \(a+b\) باید کمینه باشد، یعنی مجموع تعداد یال‌های حذف‌شده و یال‌های اضافه‌شده باید کمینه باشد.