410002 - 乒乓球队

乒乓球队中有N名男运动员和M名女运动员,由于某种原因,在混双比赛中,某些男运动员和某些女运动员不能配对比赛,这使得教练很苦恼,他希望你能帮他找出一种最优的配对方案,组成尽可能最多的混双配对。

Input

第一行三个正整数N,M,K(N+M≤1 000),表示男运动员个数、女运动员个数和可配对数。以下K行,每行两个整数a,b,表示男运动员a可与女运动员b配对比赛。

Output

只有一个整数,为最多的混双配对。

Examples

Input

5 4 14
1 1
1 2
2 3
3 2
4 2
4 3
4 4
5 4
5 2
5 3
3 3
2 4
1 3
2 1

Output

4
Time Limit 1 second
Memory Limit 128 MB
Discuss Stats
上一题 下一题