6. 신호등 (GRASKRIZJA)

프로그램 명: coci_graskrizja(special judge)

제한시간: 1 초

//..아직 sj 가 되지 않았습니다

캔디 마을은 이제 대규모 도시가 되었다. 캔디 마을의 도로는 직사각형 격자 형태로 개발되었는데, 50,000개의 남북방향 도로(x-좌표 1~50,000으로 매겨짐)와 50,000개의 동서방향 도로(y-좌표 1~50,000으로 매겨짐)가 생겼다. 모든 도로는 양방향 통행이 가능하다.

캔디 마을이 규모가 커졌지만, 시민의 수준이 그만큼 발달하지 못했기 때문에 교통 시스템이 엉망이 되었다. 따라서 캔디 마을 시장은 N개의 교차로(가로 도로와 세로 도로가 만나는 지점)에 신호등을 설치했다. 신호등이 설치됨에 따라, 신호등이 설치된 교차로에서만 좌회전 또는 우회전을 하는 ‘안전한 경로’가 여럿 생기게 되었다.

모든 경로가 안전하다고 보장할 수는 없지만, 캔디 마을 시장은 출발 지점과 도착 지점이 모두 신호등이 있는 교차로일 때에 한해서 최단 경로 중 하나 이상의 안전한 경로가 있기를 바란다. 따라서 당신은 캔디 마을 시장의 요구에 맞게 신호등을 더 설치해야 한다. 허나, 예산은 한정되어 있기 때문에 700,000개 이상 설치할 수 없다.

캔디 마을 시장을 도와 조건에 맞게 신호등을 설치하는 위치를 구하는 프로그램을 작성하여라.

입력 형식

첫 번째 줄에는 신호등의 수 N이 주어진다. (2 ≤ N ≤ 50,000)
두 번째 줄부터 N개의 줄에는 설치된 신호등이 위치한 교차로의 세로 도로 의 번호 X와 가로 도로의 번호 Y (1 ≤ X, Y ≤ 50,000)가 주어진다. 한 교차로에는 최대 한 개의 신호등이 있을 수 있다.

출력 형식

새로 설치할 신호등의 위치를 한 줄에 하나씩 출력한다. 같은 위치에 여러 개의 신호등을 설치해도 무방하며, 새로운 신호등은 700,000개보다 적어야 한다. 답이 여러 개이면 그중 아무거나 출력한다.

Peatown has become a metropolis. We can observe it as a rectangular grid of streets. There are fifty thousand vertical streets running north-south (labeled with x-coordinates from 1 to 50 000) and fify thousand horizontal streets running east-west (labeled with y-coordinates from 1 to 50 000). All streets are two-way 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 pea-brained so help the residents of Peatown!

INPUT

The first line of input consists of an integer N (2 ≤ N ≤ 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 ≤ X, Y ≤ 50 000), coordinates of the vertical and horizontal streets which intersect in that crossroads. All traffic lights will be unique.

OUTPUT

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.

SAMPLE TESTS

input 
 
2 
1 1 
3 3 
 
output 
 
1 3 

input 
 
3 
2 5 
5 2 
3 3 
 
output 
 
3 5 
5 3 
 
input 
 
5 
1 3 
2 5 
3 4 
4 1 
5 2 
 
output 
 
1 5 
3 3 
3 5 
4 2 
4 3

출처:coci/2013-2014/contest6 6 번
번역:functionx

[질/답] [제출 현황] [푼 후(0)]

[ 채 점 ] [홈으로] [뒤 로]