درخت‌سازی


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

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

رئوس گراف با اعداد طبیعی از 11 تا nn شماره‌گذاری شده‌اند.

ورودی🔗

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

در ادامه mm خط در ورودی آمده‌است. در iiامین خط از mm خط بعدی، دو عدد طبیعی xix_i و yiy_i نابرابر با یک فاصله بینشان آمده‌است که نشان می‌دهد یال (xi,yi)(x_i, y_i) در گراف وجود دارد.

به ازای هر ii معتبر داریم: 1xi,yin 1 \leq x_i, y_i \leq n xiyi x_i \neq y_i

خروجی🔗

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

مثال🔗

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

3 2
1 2
2 3
Plain text

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

0 0
Plain text

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

3 3
1 2
2 3
3 1
Plain text

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

1 0
1 3
Plain text

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

4 0
Plain text

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

0 3
1 2
2 3
3 4
Plain text

نکات🔗

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