题目描述

给定一个二分图，该二分图的左部节点集合有 $n$ 个节点，右部节点集合有 $m$ 个节点，边数为 $e$。求该二分图的最大匹配数。二分图最大匹配是指在二分图的所有匹配中，边数最多的匹配。

输入描述

第一行输入三个整数 $n$，$m$ 和 $e$，分别表示左部节点数、右部节点数和边数，以空格分隔。 接下来 $e$ 行，每行输入两个整数 $u$ 和 $v$，表示左部节点 $u$ 和右部节点 $v$ 之间有一条边（$1 \leq u \leq n$，$1 \leq v \leq m$），以空格分隔。

输出描述

输出该二分图的最大匹配数。

数据范围

$1 \le n,m \le 500,\ 0 \le e \le n \times m$

输入输出样例

样例 1

输入：

3 3 4
1 1
1 2
2 2
3 3

输出：

3

解释：匹配方案 1→1、2→2、3→3，共3组匹配。

样例 2

输入：

2 2 3
1 1
1 2
2 1

输出：

2

解释：匹配方案 1→2、2→1，全部匹配成功。

样例 3

输入：

2 2 0

输出：

0

解释：不存在任何边，无法形成匹配。

样例 4

输入：

3 2 3
1 1
2 1
3 2

输出：

2

解释：匹配方案 1→1、3→2，左部节点2无匹配，最大匹配数量为2。