题目描述

有很多纵横交错的街道，街道均为双向。水平和垂直街道的交叉口称为十字路口。

现决定在 $N$ 个十字路口设红绿灯，若两个十字路口间的一条路无红绿灯则转弯危险，反之安全。

只要在每两个红绿灯之间有至少一条最短的路径是安全的就符合要求，你需要设置一些额外的红绿灯以满足要求。

输入格式

第一行输入由整数 $N$ 组成，即最初的红绿灯数。

接下来 $N$ 行，每行两个整数 $x_i$ 和 $y_i$，表示第 $i$ 个红绿灯的坐标。

所有的红绿灯的坐标互不相同。

输出格式

输出新红绿灯的位置，允许在同一位置放置多个红绿灯，新增红绿灯数量必须少于 $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

提示

【数据规模与约定】

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

【说明】

题目译自 COCI2013-2014 CONTEST #6 T6 GRAŠKRIŽJA。