Ghép Đôi Sân Khấu · canuc80k4906

Câu lạc bộ có $n$ bạn thuộc nhóm $A$ và $m$ bạn thuộc nhóm $B$ . Ban tổ chức đã ghi nhận $k$ cặp có thể cùng biểu diễn.

Hãy chọn nhiều cặp nhất có thể. Mỗi cặp phải gồm một người từ mỗi nhóm, phải nằm trong danh sách cho trước, và mỗi người chỉ được xuất hiện trong tối đa một cặp. Nếu có nhiều cách tối ưu, bạn có thể in bất kỳ cách nào.

Input

Dòng đầu chứa ba số nguyên $n, m, k$ .
Mỗi trong $k$ dòng tiếp theo chứa $a, b$ , biểu diễn một cặp hợp lệ giữa người $a$ của nhóm $A$ và người $b$ của nhóm $B$ . Một cặp có thể xuất hiện lặp trong input.

Output

Dòng đầu in số cặp lớn nhất $r$ .
Tiếp theo in đúng $r$ dòng, mỗi dòng gồm $a, b$ của một cặp được chọn.

Constraints

$1 \leq n, m \leq 500$ .
$1 \leq k \leq 1000$ .
$1 \leq a \leq n$ .
$1 \leq b \leq m$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $n, m \leq 8$ và $k \leq 20$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Ba cặp được in dùng ba người khác nhau ở mỗi phía. Nhóm $B$ chỉ có ba người nên không thể chọn hơn $3$ cặp.

Phân tích: Đây là matching hai phía. Tạo một nút cho mỗi người; mỗi đơn vị flow đi theo đường S -> A_i -> B_j -> T biểu diễn việc chọn cặp (i,j).
Thuật toán: Nối S tới mọi nút nhóm A capacity 1, nối mỗi cặp tiềm năng từ A sang B capacity 1, và nối mọi nút nhóm B tới T capacity 1. Chạy Dinic, sau đó duyệt các cạnh A-B gốc; cạnh mang một đơn vị flow là cặp được chọn.
Chứng minh: Mọi matching kích thước r tạo được flow nguyên giá trị r. Ngược lại, các capacity biên bằng 1 bảo đảm một flow nguyên không dùng một người hai lần, nên các cạnh A-B mang flow tạo thành matching cùng kích thước. Do đó maximum flow và maximum matching có cùng giá trị, còn phần khôi phục cho một phương án tối ưu.
Độ phức tạp: Cận Dinic tổng quát là O(V^2E), với V=n+m+2, E=O(n+m+k); bộ nhớ O(V+E).