eolymp
bolt
Try our new interface for solving problems
Məsələlər

Türmə yerdəyişməsi

Türmə yerdəyişməsi

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Nizamsızlıq və qaçma cəhddini azaltmaq üçün məhbusların sayına görə bərabər sayda tutumu olan iki qonşu həbsxananın müdiriyyəti öz məbuslarını öz aralarında dəyişdirmək qərarına gəldilər. Onlar bir həbsxananın məhbuslarının yarısını digərinin yarısı ilə dəyişdirmək istəyirlər. Lakin məhbusların cinayət tarixləri haqqında arxıv məlumatlarından onlar bilirlər ki, bəzi məhbus cütlüklüərini eyni bir kamerada saxlamaq təhlükəlidir və buna görə də onlar indi ayrı saxlanılır, yəni, hər bir belə məhbus cütlüyü üçün məhbuslardan biri öz cəzasını birinci həbsxanada, digəri isə ikincisində çəkir. Müdiriyyətlər bu cütlüklərin ayrıca müxtəlif həbsxanalarda saxlanılmasının vacibliyi haqqında razılığa gəldilər ki, bu da yerdəyişməyə cəhd məsələsini bir az çətinləşdirir. İş orasındadır ki, onlar tezliklə görəcəklər ki, bəzən məhbusların yarısı üçün arzu edilən bütün yerdəyişmələri etmək mümkün olmayacaq. Hər dəfə belə hadisə baş verdiyi zaman onlar elə yerdəyişməyə razılaşmalıdırlar ki, mümkün qədər məhbusların yarısına yaxın sayda yerdəyişmə etmək imkanı olsun.

Giriş verilənləri

Giriş faylının birinci sətrində növbəti test hallarının sayını göstərən yeganə n ədədi verilir. Hər bir test halı mənfi olmayan iki mr tam ədədlərini ehtiva edən sətirlə başlayır ki, burada 1 < m < 200 hər iki həbsxanadakı məhbusların sayı, r isə məhbuslar arasında təhlükəli cütlərin sayıdır. Daha sonra 1-dən r-ə qədər diapazonda tam ədəd olan x_i y_i cütlüklərini ehtiva edən r sətir gəlir. Bu onu göstərir ki, birinci həbsxananın x_i məhbusu ikinci həbsxananın y_i məhbusu ilə eyni bir kamerada saxlanılmamalıdır.

Çıxış verilənləri

Hər bir test halı üçün elə ən böyük km/2 tam ədədini ehtiva edən tək sətir verin ki, istənilən təhlükəli cütlükdən olan iki məhbusu eyni bir həbsxanada saxlamamaq üçün birinci həbsxananın k sayda məhbusunu ikinci həbsxananın k sayda məhbusu ilə dəyişmək mümkün olsun.

Nümunə

Giriş verilənləri #1
3
101 0
3 3
1 2
1 3
1 1
8 12
1 1
1 2
1 3
1 4
2 5
3 5
4 5
5 5
6 6
7 6
8 7
8 8
Çıxış verilənləri #1
50
0
3