题目描述

给定一个二分图，左部有 $n$ 个点（编号 $1$ 到 $n$），右部有 $m$ 个点（编号 $1$ 到 $m$），以及 $e$ 条边。求该二分图的最大匹配数（即最多能选出多少条互不共享端点的边）。

输入格式

第一行三个整数 $n, m, e$，分别表示左部点数、右部点数和边数。

接下来 $e$ 行，每行两个整数 $u, v$，表示左部点 $u$ 和右部点 $v$ 之间有一条边。

输出格式

输出一行一个整数，表示最大匹配数。

样例

1 1 1
1 1

1

4 2 7
3 1
1 2
3 2
1 1
4 2
4 1
1 1

2

提示

对于 $100\%$ 的数据，$1 \le n, m \le 500$，$1 \le e \le 5 \times 10^4$，$1 \le u \le n$，$1 \le v \le m$。

输入可能包含重边。