Минимакс cütləşmə#640
Tam bipartit qraf verilir, burada hər iki hissədə ədəd qraf düyünü mövcuddur. Hər bir düyünün bir tam ədədi çəkisi var. Kənarın çəkisi, onu birləşdirən iki düyünün çəkilərinin hasilinə bərabərdir.
Qrafta uyğunluq — elə kənarlar toplusudur ki, heç biri ümumi düyünə malik deyil. Uyğunluq o zaman mükəmməl sayılır ki, o, qrafdakı bütün düyünləri əhatə etsin, yəni hər bir düyün uyğunluqdakı kənarlardan birinə aid olsun.
Sizdən tələb olunur ki, mükəmməl minimaks uyğunluq tapasınız; yəni, elə bir mükəmməl uyğunluq seçməlisiniz ki, seçilmiş kənarlar arasında maksimum çəki mümkün qədər kiçik olsun.
Birinci sətrdə bir tam ədəd (1 \leq N \leq 10^5) verilir. İkinci sətrdə birinci hissədəki düyünlərin çəkiləri olan ədəd tam ədəd verilir; onların hər birinin modulu 10^9-u keçmir. Üçüncü sətrdə eyni şəkildə ikinci hissədəki düyünlərin çəkiləri olan ədəd tam ədəd verilir. Hər bir hissədəki düyünlər -dən -ə qədər nömrələnir.
Bir tam ədəd çap edin — mükəmməl minimaks uyğunluğun çəkisi, yəni seçilmiş kənarların ən böyüyünün çəkisi. İkinci sətrdə isə uyğunluğun təsvirini verin: ədəd tam ədəd, burada -ci ədəd göstərir ki, birinci hissənin -ci düyünü hansı ikinci hissənin düyünü ilə uyğunluqdadır.
Nümunə 1