Problem Description

There are many crisscrossing streets, and all streets are two-way. The intersection of a horizontal street and a vertical street is called a crossroads.

Now we will place traffic lights at $N$ crossroads. If a road between two crossroads has no traffic light, then turning is dangerous; otherwise, it is safe.

It is considered acceptable as long as, between every pair of traffic lights, there exists at least one shortest path that is safe. You need to add some extra traffic lights to meet this requirement.

Input Format

The first line contains an integer $N$, which is the initial number of traffic lights.

The next $N$ lines each contain two integers $x_i$ and $y_i$, representing the coordinates of the $i$-th traffic light.

All traffic lights have distinct coordinates.

Output Format

Output the positions of the new traffic lights. It is allowed to place multiple traffic lights at the same position. The number of added traffic lights must be less than $7\times 10^5$.

2
1 1
3 3 

1 3

3
2 5
5 2
3 3 

3 5
5 3 

5
1 3
2 5
3 4
4 1
5 2 

1 5
3 3
3 5
4 2
4 3

Hint

Constraints

• $2 \leq N \leq 5\times 10^4$.
• $1 \leq x_i,y_i \leq 5\times 10^4$.

Notes

This problem is translated from COCI2013-2014 CONTEST #6 T6 GRAŠKRIŽJA.

Translated by ChatGPT 5