19522번 - Nice Set of Points 스페셜 저지다국어

Consider a set of points. You can move directly between two points if their x-coordinates are the same or their y-coordinates are the same. A set of points is called nice if for any two points in the set, the length of the shortest (direct or indirect) path is equal to the manhattan distance between them.

You are given $N$ points. The $i$-th point is at $(x_i, y_i)$.

You are allowed to add up to $10000 - N$ points. Convert the given set of points into a nice set.

$N$
$x_1$  $y_1$
$x_2$ $y_2$
$\vdots$
$x_N$ $y_N$

Let $M (0 \leq M \leq 10000 - N)$ be the number of added points, and $(s_1, t_1), \ldots, (s_M, t_M)$ be their coordinates. After adding these $M$ points to the set, you get $N + M$ points. These $N+M$ points must be pairwise distinct, and this set must be nice. The coordinates must be integers.

Output the answer in the following format.

$M$
$s_1$ $t_1$
$s_2$ $t_2$
$\vdots$
$s_N$ $t_M$

If there are multiple possible solutions, output any.

• $2 \leq N \leq 1000$
• $1 \leq x_i, y_i \leq 1000$
• The points are pairwise distinct.
• Under these constraints, it is guaranteed that at least one solution exists.
• All values in the input are integers.

In Sample 1, if you add $(1, 2)$, you can move between $(1, 1)$ and $(2, 2)$ via $(1, 2)$.