考虑一个形状为具有 $2N$ 个顶点的凸多边形的平面图。每个顶点按顺时针方向从 $1$ 到 $2N$ 进行编号。目前，沿凸多边形的边界有 $2N$ 条双向边。换句话说，对于每个 $1 \le i \le 2N$，顶点 $i$ 和顶点 $(i \bmod 2N) + 1$ 之间都有一条边相连。

每个顶点都染有 $1$ 到 $N$ 之间的 $N$ 种颜色之一。对于每种颜色 $i$（$1 \le i \le N$），恰好有两个顶点的颜色为 $i$。颜色为 $i$ 的两个顶点的编号分别为 $x_i$ 和 $y_i$。

我们希望向该图中添加恰好 $2N - 3$ 条双向边。添加后，必须满足以下条件：

• 每条边必须通过一条线段连接两个不同的顶点。
• 对于任意两个不同的顶点，它们之间最多只能有一条边直接相连。
• 该图必须仍然是平面图。

设 $dist(a, b)$ 为顶点 $a$ 和 $b$ 之间的最短路径长度。在所有满足上述条件的加边方案中，找到一种方案，使得 $\sum_{i=1}^N dist(x_i, y_i)$ 最小。

输入格式

第一行包含一个整数 $N$（$2 \le N \le 200\,000$）。

接下来的 $N$ 行，每行包含两个整数 $x_i, y_i$，表示颜色为 $i$ 的两个顶点的编号（$1 \le x_i, y_i \le 2N$）。

输出格式

第一行输出 $\sum_{i=1}^N dist(x_i, y_i)$ 的最小可能值。

接下来的 $2N - 3$ 行，每行输出两个整数，表示每条新添加的边的两个端点。

如果有多个答案，输出其中任意一个即可。

样例

输入样例 1

3
1 3
2 5
6 4

输出样例 1

5
1 3
4 1
4 6

说明