Cütləşmə
Qraf ikiqatlı adlanır, əgər onun zirvələr çoxluğu V kəsişməyən iki çoxluğa - A və B - bölünə bilirsə, belə ki, qrafın hər bir kənarının ucları bu iki çoxluğun fərqli elementlərində yerləşir. Qrafda uyğunluq, kənarların çoxluğunun E alt çoxluğu S adlanır ki, bu alt çoxluqda heç bir ümumi zirvə yoxdur (yəni, S daxilindəki hər hansı iki kənar e_{1 }= (u_1, v_1) və e_{2 }= (u_2, v_2) üçün u_{1 }= u_2, u_{1 }= v_2, v_{1 }= u_2 və v_{1 }= v_2 şərtləri ödənilmir).
Sizin vəzifəniz verilmiş ikiqatlı qrafda maksimal uyğunluğu tapmaqdır. Maksimal uyğunluq, mümkün olan ən çox sayda kənardan ibarət olan uyğunluqdur.
Giriş verilənləri
Giriş faylının birinci sətiri iki tam ədəd N və M (1 ≤ N, M ≤ 250) - A və B çoxluqlarında zirvələrin sayını ehtiva edir. Sonrakı N sətir qrafın kənarlarının təsvirini ehtiva edir. (i+1)-ci sətirdə A çoxluğunun i-ci zirvəsi ilə birləşən B çoxluğunun zirvələrinin siyahısı verilir. Siyahı 0 rəqəmi ilə tamamlanır. A və B çoxluqlarında zirvələrin nömrələnməsi müstəqildir (zirvələr 1-dən nömrələnir).
Çıxış verilənləri
Çıxış faylının birinci sətiri maksimal uyğunluqda olan kənarların sayını göstərən bir tam ədəd L ehtiva etməlidir. Sonrakı L sətirin hər biri uyğunluğun bir kənarının təsvirini ehtiva etməlidir - A çoxluğunda zirvənin nömrəsi və B çoxluğunda zirvənin nömrəsi olan iki tam ədəd u_i və v_i.