题目描述

给定一个简单多边形。简单多边形指任意两条非相邻边互不接触，相邻边只在公共端点处相交。

一个有 $n$ 个顶点的简单多边形可以通过添加 $n-3$ 条连接原多边形顶点的线段，被划分成若干个三角形。所添加的线段之间不能相交，也不能与多边形边界相交，除了允许在公共端点处相交。

多边形的顶点按边界顺序编号为 $0,1,\ldots,n-1$，第 $i$ 个顶点坐标为 $(x_i,y_i)$，并存在边 $(i,(i+1)\bmod n)$。

你需要输出一种三角剖分。每条新加入的对角线记为一对顶点编号 $(u,v)$，要求 $u<v$。将全部 $n-3$ 条对角线按 $u$ 升序、再按 $v$ 升序排列，得到一个序列。

如果存在多种合法三角剖分，要求输出上述序列按字典序最小的那一个。也就是说，比较两个方案时，找到第一个不同的二元组，优先选择 $u$ 更小的方案；若 $u$ 相同，则优先选择 $v$ 更小的方案。

输入格式

第一行一个整数 $n$，表示多边形顶点数。

接下来 $n$ 行，第 $i+1$ 行两个整数 $x_i,y_i$，表示编号为 $i$ 的顶点坐标。

输出格式

第一行输出一个整数 $n-3$，表示加入的对角线数量。

接下来 $n-3$ 行，每行两个整数 $u,v$，表示一条对角线。输出顺序必须先按 $u$ 升序，再按 $v$ 升序，并且整个对角线序列必须是所有合法三角剖分中字典序最小的。

样例 1

输入

4
0 0
10 0
10 10
0 10

输出

1
0 2

样例 2

输入

4
0 0
10 0
10 10
8 2

输出

1
1 3

数据范围

• $4\le n\le50$；
• $-1000\le x_i,y_i\le1000$；
• 输入保证构成简单多边形；
• 每条边长度严格大于 $0$；
• 任意两条相邻边不平行。