Description

有 $n$ 个用弹性材料制成的螺母，$m$ 个钢制螺栓。螺栓编号从 $1$ 到 $m$，螺母编号从 $m + 1$ 到 $m + n$。给出螺母与螺栓的匹配情况，如：$u$ ，$v$ 表示螺栓 $u$ 与螺母 $v$ 可以匹配。

请找出最佳的匹配方案，使得匹配数最大。

注意：每个螺母至多匹配一个螺栓

Input Format

第一行输入两个整数 $m$ 和 $n$ ($0<m+n\le 100, m\ne 0,n\ne 0$)

从第二行开始，每行输入两个整数 $u$，$v$ ($0<u\le m,m<v\le m+n)$。题目保证没有重复的 $u$，$v$ 关系

最后一行输入$-1$ $-1$ 代表输入结束

Output Format

第一行输出总的匹配对数 $sum$

接下来 $sum$ 行

每行输出两个整数 $u$，$v$，表示匹配方案

5 7
1 6
1 7
1 8
2 6
2 9
3 12
4 11
5 6
5 8
-1 -1

5
1 7
2 6
3 12
4 11
5 8

Hint

本题存在SPJ

Source

Online Judge http://127.0.0.1