题目描述

Droopland 是一个具有 $2N$ 个顶点的凸多边形王国。每个顶点上有一座房屋，按顺时针方向编号为 $1,2,\ldots,2N$。

多边形边界上的相邻房屋之间已经修建了双向道路：对于 $1\le i<2N$，房屋 $i$ 与房屋 $i+1$ 相连，同时房屋 $1$ 与房屋 $2N$ 相连。

王国中有 $N$ 位居民，编号为 $1,2,\ldots,N$。每位居民恰好拥有两座房屋，并且每座房屋都有且仅有一位主人。设第 $i$ 位居民拥有的房屋编号为 $x_i,y_i$。

你需要再修建恰好 $2N-3$ 条双向道路，并满足：

1. 每条道路是一条连接两座不同房屋的线段；
2. 任意一对房屋之间至多有一条道路，包括原有边界道路；
3. 任意两条道路除公共端点外不能相交。

设 $\operatorname{Dist}(a,b)$ 为从房屋 $a$ 到房屋 $b$ 最少需要经过的道路条数。请构造道路，使

最小。

输入格式

第一行包含整数 $N$。

接下来 $N$ 行，第 $i$ 行包含两个整数 $x_i,y_i$，表示第 $i$ 位居民拥有的两座房屋。

数据范围：

所有 $2N$ 个房屋编号在这些数对中各出现恰好一次。

输出格式

第一行输出最小的距离总和。

接下来输出 $2N-3$ 行，每行两个整数 $a,b$，表示新建一条连接房屋 $a$ 与房屋 $b$ 的道路。

若存在多种最优方案，输出任意一种即可。

样例

输入

3
1 3
2 5
6 4

输出

5
1 3
1 4
6 4

一种合法的最优道路布局如下：

在该方案中，$\operatorname{Dist}(1,3)=1$，$\operatorname{Dist}(4,6)=1$，$\operatorname{Dist}(2,5)=3$，总和为 $5$。