You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-1696 题。

题目描述

学校里有 $n$ 个男孩和 $m$ 个女孩。下周将举办一场学校舞会。一对舞伴由一个男孩和一个女孩组成，共有 $k$ 对潜在的舞伴。

你的任务是找出最多能组成多少对舞伴，并展示这些舞伴的配对方式。

输入格式

第一行包含三个整数 $n$、$m$ 和 $k$：分别表示男孩的数量、女孩的数量和潜在的舞伴对数。男孩编号为 $1,2,…,n$，女孩编号为 $1,2,…,m$。

接下来有 $k$ 行，每行包含两个整数 $a$ 和 $b$：表示男孩 $a$ 和女孩 $b$ 愿意一起跳舞。

输出格式

首先输出一个整数 $r$：表示最多可以组成的舞伴对数。

接着输出 $r$ 行，分别描述每一对舞伴的配对。你可以输出任何有效的解决方案。

样例

3 2 4
1 1
1 2
2 1
3 1

2
1 2
3 1

说明/提示

$1 \leq n,m \leq 500$；

$1 \leq k \leq 1000$；

$1 \leq a \leq n$；

$1 \leq b \leq m$。