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

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

رئوس گراف با اعداد طبیعی از $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$ باید کمینه باشد، یعنی مجموع تعداد یال‌های حذف‌شده و یال‌های اضافه‌شده باید کمینه باشد.