#T2117. 校园舞会(School Dance)

校园舞会(School Dance)

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

板块: Graph Algorithms

时限: 1.00 s | 内存: 512 MB

题目描述

一所学校有 nn 名男生和 mm 名女生。下周将组织一场校园舞会。一支舞伴由一男一女组成,共有 kk 对潜在组合。

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

输入

第一行输入包含三个整数 nn、mm 和 kk:男生数量、女生数量和潜在组合数。男生编号为 1,2,…,n1,2,\dots,n,女生编号为 1,2,…,m1,2,\dots,m。

之后有 kk 行描述潜在组合。每行包含两个整数 aa 和 bb:男生 aa 和女生 bb 愿意一起跳舞。

输出

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

数据范围

1≤n,m≤5001 \le n,m \le 500 1≤k≤10001 \le k \le 1000 1≤a≤n1 \le a \le n 1≤b≤m1 \le b \le m

样例输入

3 2 4
1 1
1 2
2 1
3 1

样例输出

2
1 2
3 1