Starfruit Ice Cream
Description
Patrick is trying to create a magical starfruit ice cream with his special blend of magical starfruit-flavored milk. Making starfruit ice cream is a very delicate process, which means he must follow a very specific procedure. Patrick has $n$ ($4 \leq n \leq 2000$) pints of starfruit milk. He is pouring them into a special square-grid-shaped bowl of size $n$ by $n$ before he freezes the milk to turn into ice cream. However, he can't just pour the milk into a random location. He must follow a specific set of rules to avoid magical disaster. Foremost, he must pour exactly one pint of milk into a grid location, no more, no less. Additionally, magical starfruit milk doesn't spread in a typical fashion. Starfruit milk poured at location will spread in 8 directions (like a star) until it hits the edge of the bowl: the four cardinal directions (up, down, left, right) and the four ordinal directions (northwest, northeast, southeast, southwest). Once again, to avoid magical disaster, starfruit milk cannot spread into another cell where milk was poured into. Finally, for larger bowls, there are $k\ \left(0 \leq k \leq \lfloor\frac{n}{400}\rfloor\right)$ specific locations that Patrick cannot pour milk into in order to appease the starfruit gods. However, it is fine if starfruit milk spreads into these locations. Help Patrick figure out which $n$ locations in the bowl he should pour the starfruit milk in order to avoid magical disaster and appease the gods.
The first line will contain an integer $n$ ($4 \leq n \leq 2000$) specifying the pints of starfruit milk and an integer $k\ \left(0 \leq k \leq \lfloor\frac{n}{400}\rfloor\right)$ specifying the number of grid locations that Patrick must avoid pouring milk into. The next $k$ lines will contain two integers, $r$ and $c$, ($1\leq r,c \leq n$) which represent a location $(r,c)$ that Patrick cannot pour milk into.
Print $n$ lines where each line has two space separated integers: $r$ and $c$ which represent the row and column that Patrick should pour milk into. Note that there are multiple solutions, but any valid solution will pass.
Input
The first line will contain an integer $n$ ($4 \leq n \leq 2000$) specifying the pints of starfruit milk and an integer $k\ \left(0 \leq k \leq \lfloor\frac{n}{400}\rfloor\right)$ specifying the number of grid locations that Patrick must avoid pouring milk into. The next $k$ lines will contain two integers, $r$ and $c$, ($1\leq r,c \leq n$) which represent a location $(r,c)$ that Patrick cannot pour milk into.
Output
Print $n$ lines where each line has two space separated integers: $r$ and $c$ which represent the row and column that Patrick should pour milk into. Note that there are multiple solutions, but any valid solution will pass.
4 0
8 0
2 1
4 2
1 3
3 4
6 1
3 2
1 3
8 4
5 5
2 6
4 7
7 8
Note
The following illustration shows one possible solution to sample test 1. Note how none of the milk spreads into another cell where milk was poured into.
