School Dance

题目描述

学校里有 $n$ 个男生和 $m$ 个女生。下周将举办一次舞会。一个舞蹈对由一名男生和一名女生组成，总共有 $k$ 个可能的配对。\n你的任务是找出最多可以组成多少对舞蹈，并展示如何达到这个数量。

输入格式

第一行输入有三个整数 $n$, $m$ 和 $k$：男生数、女生数和可能的配对数。男生编号为 $1,2,\dots,n$，女生编号为 $1,2,\dots,m$。\n接下来有 $k$ 行描述可能的配对。每行有两个整数 $a$ 和 $b$：男生 $a$ 和女生 $b$ 愿意一起跳舞。

输出格式

首先输出一个整数 $r$：最多可以组成的舞蹈对数。随后输出 $r$ 行描述这些配对。你可以输出任何一个有效的解。

3 2 4
1 1
1 2
2 1
3 1

2
1 2
3 1

提示

$1 \le n,m \le 500$ $1 \le k \le 1000$ $1 \le a \le n$ $1 \le b \le m$

标签: CSES1696|图论

来源

CSES1696|图论