P6876 [COCI 2013/2014 #6] GRAŠKRIŽJA (Looking for SPJ)

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.

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 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$.

#### 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](https://hsin.hr/coci/archive/2013_2014/) [CONTEST #6](https://hsin.hr/coci/archive/2013_2014/contest6_tasks.pdf) _T6 GRAŠKRIŽJA._** Translated by ChatGPT 5