Statement

Given N (N <= 10^5) cats and M (M <= 10^5) dogs with their tag number (<= 10^9). A cat and a dog can be matched if they have the different tag number. Compute the greatest numbers of pairs that can be matched and print out the links.

Input

3 3 (N, M)

1 1 2 (tag number of N cats)

2 1 1 (tag number of M dogs)

Output

2

1 1

3 2

Explain

• The first cat(tag number: 1) matches with the first dog(tag number: 2)

• The third cat(tag number: 2) matches with the second dog(tag number: 1)

At first glance, I thought it was a simple maximum matching problem but then I realize that time complexity to build such bigraph is O(N * M). Are there other approaches to do it?