Cho một đồ thị hai phía gồm \(N\) đỉnh ở tập trái và \(M\) đỉnh ở tập phải, cùng \(K\) cạnh nối giữa chúng. Một tập đỉnh được gọi là phủ cạnh (vertex cover) nếu mỗi cạnh của đồ thị đều có ít nhất một đầu mút thuộc tập đó. Hãy tìm kích thước nhỏ nhất của một tập phủ cạnh.

Định dạng đầu vào

• Dòng đầu chứa ba số nguyên \(N, M, K\) (\(1 \le N, M \le 2000\), \(0 \le K \le 50000\)).
• \(K\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) (\(1 \le u \le N, 1 \le v \le M\)) mô tả cạnh nối đỉnh \(u\) (trái) với đỉnh \(v\) (phải).

Định dạng đầu ra

• Một số nguyên duy nhất là kích thước tập phủ cạnh nhỏ nhất.

Ràng buộc

Ví dụ

Input:

3 3 5
1 1
1 2
2 2
2 3
3 3

Output:

2