Maksimal buxar birləşməsi

Qraf $G=(V,E)$ iki hissəli adlanır, əgər onun $V$ zirvələr çoxluğunu $A$ və $B$ alt çoxluqlarına elə bölmək mümkündürsə ki, $E$-dən olan hər hansı bir kənar $A$-dan bir zirvəni $B$-dən bir zirvə ilə birləşdirir.

Cütləşmə $P$ adlanır, əgər $E$-dən olan hər hansı bir alt çoxluq elədir ki, bu çoxluqdan olan heç bir iki kənar ümumi zirvəyə malik deyil.

Maksimal cütləşmə — bu, maksimal sayda kənarları olan cütləşmədir.

Verilmiş iki hissəli qrafda maksimal cütləşməni tapın.

Giriş verilənləri

Birinci sətirdə $n,m$ və $k(1\le n,m\le 100,1\le k\le 10000)$ üç ədəd verilir, burada $n$ — $A$ çoxluğunda olan zirvələrin sayı, $m$ — $B$ çoxluğunda olan zirvələrin sayı və $k$ — qrafda olan kənarların sayıdır. Növbəti $k$ sətirdən hər biri iki ədəd $u_i$ və $v_i$ ehtiva edir, bu o deməkdir ki, $A$ çoxluğundan olan $u_i$ zirvəsi $B$ çoxluğundan olan $v_i$ zirvəsi ilə birləşir. $A$ və $B$ çoxluqlarında olan zirvələr müstəqil olaraq, birdən başlayaraq nömrələnir. Bütün giriş ədədləri tamdır.

Çıxış verilənləri

Birinci sətirdə maksimal cütləşmədə olan $l$ kənarların sayını çıxarın. Sonra $l$ sətir çıxarın, hər biri iki ədəd ehtiva edir: $a$ və $b$, burada $a$ — $A$ çoxluğundan olan zirvə və $b$ — cütləşmədə ona uyğun olan $B$ çoxluğundan olan zirvədir. Seçilmiş kənarlar maksimal cütləşmə təşkil etməlidir.

Nümunələr