链接: https://cses.fi/problemset/task/1696

板块: Graph Algorithms

时限: 1.00 s ｜ 内存: 512 MB

题目描述

一所学校有 $n$ 名男生和 $m$ 名女生。下周将组织一场校园舞会。一支舞伴由一男一女组成，共有 $k$ 对潜在组合。

你的任务是求出最多的舞伴数量，并展示如何达到这个数量。

输入

第一行输入包含三个整数 $n$、$m$ 和 $k$：男生数量、女生数量和潜在组合数。男生编号为 $1,2,\dots,n$，女生编号为 $1,2,\dots,m$。

之后有 $k$ 行描述潜在组合。每行包含两个整数 $a$ 和 $b$：男生 $a$ 和女生 $b$ 愿意一起跳舞。

输出

先输出一个整数 $r$：最多的舞伴数量。之后输出 $r$ 行描述这些组合。你可以输出任意合法解。

数据范围

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

样例输入

3 2 4
1 1
1 2
2 1
3 1

样例输出

2
1 2
3 1