题目描述

给定一张左侧有 $nl$ 个点、右侧有 $nr$ 个点、$m$ 条边的二分图，求一组它的最大匹配。

输入格式

第一行三个整数 $nl$，$nr$，$m$。

接下来 $m$ 行，每行两个整数 $u_i$，$v_i$，表示有一条左侧第 $u_i$ 个点连向右侧第 $v_i$ 个点的边。

输出格式

第一行一个整数表示最大匹配数。

2 2 3
1 1
1 2
2 1

2

2 2 2
1 1
2 1

1

15 15 30
4 14
6 1
14 7
7 8
1 12
15 8
8 10
6 10
6 2
6 12
5 1
5 14
11 10
9 9
7 12
11 13
5 9
6 9
9 1
5 8
10 13
1 13
10 3
11 7
10 8
9 5
12 13
11 6
12 15
14 4

12

15 15 40
6 10
3 10
2 2
6 5
1 3
11 7
5 8
14 2
10 5
9 15
15 13
13 14
8 10
9 10
15 1
10 2
7 1
3 8
12 3
12 10
11 4
14 11
4 13
7 11
14 15
7 13
12 7
11 6
12 15
2 9
9 9
6 13
1 9
6 15
4 4
14 12
5 4
14 5
12 9
2 10

15

15 15 2
14 1
14 2

1

提示

对于所有数据，$1\leq nl,nr\leq 500$，$1\leq m\leq 2.5\times 10^5$。