\(6^{th}\) round, March \(8^{th}\), 2014

Peatown has become a metropolis. We can observe it as a rectangular grid of streets. There are fifty
thousand vertical streets running nor\(th-so\)uth (labeled with \(x-co\)ordinates from 1 to 50 000) and fify
thousand horizontal streets running ea\(st-we\)st (labeled with \(y-co\)ordinates from 1 to 50 000). All streets
are t\(wo-wa\)y streets. An intersection of a horizontal and vertical street is called a crossroads.
Residents of Peatown are very irresponsible and reckless. They drive like idiots so the mayor of
Peatown has decided to place traffic lights on N crossroads. A path between two crossroads is
dangerous if there is a turn without a traffic light. Otherwise it is harmless.
It is not possible to ensure that all paths are harmless, but the mayor of Peatown is satisfied if between
each two traffic lights at least one of the shortest paths is harmless. Unfortunately, the current
distribution of traffic lights is too dangerous. Your task is to place additional traffic lights (less than
700 000 of them) so that the set of traffic lights (which contains both new and old traffic lights) meets
the mayor's requirement. Surely you're not p\(ea-br\)ained so help the residents of Peatown!

The first line of input consists of an integer N (\(2 \le N \le 50\,000\)), the number of initially placed traffic
lights.
Each of the following N lines contains a location of one traffic light, represented with integers X and Y
(\(1 \le X\), \(Y \le 50\,000\)), coordinates of the vertical and horizontal streets which intersect in that
crossroads. All traffic lights will be unique.

Output the locations of new traffic lights, each in its own line.
Placing multiple traffic lights on the same location is allowed.
The number of new traffic lights must be smaller than 700 000.

생성자가 기록되지 않았습니다.

출처 COCI 2013/2014 Contest 6