题目描述

给定一张二分图：左部有 $n$ 个点，编号 $1\sim n$；右部有 $m$ 个点，编号 $1\sim m$。图中共有 $e$ 条边，每条边给出它连接的一个左部点与一个右部点。

一个匹配指的是一组边，其中任意两条边都没有公共端点。请你求出最大匹配的大小，并按左部点编号升序输出任意一组最大匹配。

输入格式

第一行三个整数 $n,m,e$。

接下来 $e$ 行，每行两个整数 $u,v$（$1\le u\le n$，$1\le v\le m$），表示一条边。可能存在重边。

输出格式

第一行一个整数 $k$，表示最大匹配的大小。

接下来 $k$ 行，每行两个整数 $u,v$，表示匹配中用到了边 $(u,v)$，按 $u$ 升序输出。

输入输出样例 #1

输入 #1

3 3 4
1 1
1 2
2 1
3 3

输出 #1

3
1 2
2 1
3 3

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n,m\le 5\times 10^4$，$0\le e\le 2\times 10^5$。