Türmə yerdəyişməsi#3500
Qiyam və qaçış cəhdlərinin riskini azaltmaq üçün eyni tutuma malik iki yaxın həbsxananın rəhbərləri məhbuslarını qarşılıqlı olaraq yenidən paylamağa qərar veriblər. Onlar bir həbsxanadakı məhbusların yarısını digər həbsxanadakı məhbusların yarısı ilə dəyişdirmək istəyirlər. Lakin məhbusların arxivdə olan cinayət tarixçələri əsasında məlumdur ki, bəzi məhbus cütlüklərini eyni həbsxanada saxlamaq təhlükəlidir. Buna görə də belə hər bir cütlükdə məhbuslardan biri birinci, digəri isə ikinci həbsxanada yerləşdirilir. Rəhbərlər bu cütlərin ayrılıqda saxlanılmasının vacibliyinə razılaşırlar və bu, yenidən yerləşdirməni bir qədər çətinləşdirir. Əslində, tezliklə aydın olur ki, bəzən bu tələb yerinə yetirilməklə məhbusların dəqiq yarısını dəyişmək mümkün olmur. Belə hallarda isə yarıya ən yaxın sayda məhbusun dəyişdirilməsi ilə kifayətlənmək lazımdır.
Girişin ilk sətrində müsbət tam ədədi verilir, bu da neçə test ssenarisinin təqdim olunacağını göstərir. Hər bir ssenari və tam ədədlərini ehtiva edən bir sətirlə başlayır, burada 1 < m < 200 (hər iki həbsxanadakı məhbusların sayı), isə məhbuslar arasındakı təhlükəli cütlüklərin sayıdır. Sonra gələn sətirdə hər birində -dən -ə kimi aralıqda olan x_i və y_i tam ədədləri verilir. Bu o deməkdir ki, birinci həbsxanadakı x_i məhbusu ikinci həbsxanadakı y_i məhbusu ilə eyni həbsxanada olmamalıdır.
Hər bir test ssenarisi üçün belə bir ədədini tapıb bir sətrə yazın (k \leq \frac{m}{2}), ki, birinci həbsxanadan məhbusu ikinci həbsxananın məhbusu ilə dəyişmək və təhlükəli sayılan heç bir məhbus cütlüyü eyni həbsxanada olmadan bu dəyişməni həyata keçirmək mümkün olsun.
Nümunə 1