+ محدودیت زمان: ۱۰ ثانیه (برای تمامی زبان‌های برنامه‌نویسی) + محدودیت حافظه: ۵۱۲ مگابایت (برای تمامی زبان‌های برنامه‌نویسی) ---------- یک گراف ساده (گرافی بدون جهت و بدون وزن و بدون یال چندگانه و بدون طوقه) به شما داده می‌شود. شما باید کم‌ترین تعداد یال ممکن را از گراف حذف کنید و کم‌ترین تعداد یال ممکن را به گراف اضافه کنید، تا این گراف تبدیل به یک درخت (گراف هم‌بند بدون دور) بشود. رئوس گراف با اعداد طبیعی از $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$ باید کمینه باشد، یعنی مجموع تعداد یال‌های حذف‌شده و یال‌های اضافه‌شده باید کمینه باشد.

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