## TLE '17 Contest 7 P5 - Willson and Mating

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Authors:
Problem type
Willson in a field with other geese. One of the others is his mate.

Willson the Canada Goose is like any other Canada Goose - he chooses a mate and sticks with her for life.

Willson and his extended family land in a large grass field after migrating back from California. There are male geese and female geese. The male goose is located at and the female goose is located at .

As a wildlife observer, you know that mating geese pairs will try to stay as close together as possible. You wonder to yourself what the mating pairs are. You do this by partitioning the geese into pairs consisting of one male goose and one female goose. Additionally, the total distance between the geese of each pair should be minimal. Can you produce such a partition?

#### Constraints

, all coordinates satisfy .

110
220

#### Input Specification

The first line of input will contain , the number of male geese and female geese.

lines of input follow. The line will contain integers and , the position of the male goose.

more lines of input follow. The line will contain integers and , the position of the female goose.

#### Output Specification

Output lines, your partition of geese. Each line should contain two integers, and , signifying that the male goose is paired with the female goose. You may output in any order and output any solution with minimal total distance. Your answer will be judged as correct if your total distance has an absolute or relative error of no more than .

#### Sample Input

2
0 0
1 0
1 1
0 1

#### Sample Output

1 2
2 1

#### Explanation for Sample Output

The distance between geese in each pair is , so the total distance is . The other possible pairing gives a total distance of .