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