背景

这是一道Special Judge题（SPJ还没有写好）

说明

一年一度的生日又到了。 小$C$准备请他的小$L$， 小$W$等众多朋友们吃蛋糕。

由于预计有$n$-2 个人在场， 小 $C$ 就买了份正$n$边形的大蛋糕。$n$个顶点上均有草莓、黄桃、 葡萄三种水果中的一种。 保证蛋糕中三种水果均出现并且任意相邻的两个顶点上水果种类不同。

小$C$现在要切$n$-2 块蛋糕， 每人一块， 他要求： 每块蛋糕都是三角形； 各个顶点上都有水果， 且包含所有的种类。

在这样苛刻的条件下， 小 $C$ 等价于要对蛋糕做一个$n$ 边形的三角剖分， 使得里面的$n$-2 个子三角形三个顶点的水果种类各异。 请你告诉他一组合法的剖分方式， 使得满足小$C$的要求。 可以证明： 在前面的保证下， 必然存在一组解。

$n$边形的三角剖分指在$n$边形内部选择$n$-3 条对角线连接后， 形成的所有 $n$-2 个三角形， 其顶点均为 $n$ 边形的顶点。 显然剖分选取的 $n$-3 条对角线两两间要么不交， 要么仅仅在端点处相交。

本题将使用 Special Judge。 只要你的答案合法、 正确， 将会获得该测试点的全部分数。

输入格式

共两行， 第一行一个正整数$n$， 表示一个正$n$边形， 顶点从 1 到 $n$按顺时针依次编号；

第二行有 $n$ 个整数 $a_i$ ， 其中用数字 1 表示草莓， 2 表示黄桃， 3 表示葡萄。$a_i$表示第 $i$个顶点上水果的种类

输出格式

共 $n$ − 3 行， 每行两个数 $u,v$， 表示剖分包括边 ($u,v$)。 你需要满足$1 ≤ u,v ≤ n$， 且$u ≠ v， u$和 $v$ 在原多边形上不相邻。

这$n$−3 条边描述了一组三角剖分， 你需要满足其是一组合法的三角剖分， 并且满足所有$n$− 2 个剖分得到的三角形， 三个顶点均含有三种水果， 否则会导致答案错误

样例

5 
1 2 3 2 3

1 3
1 4

【 样例 1 解释】

如图所示， 使用红色表示草莓， 黄色表示黄桃， 紫色表示葡萄

6
1 2 3 1 2 3

2 4
4 6
6 2

【 样例 2 解释】

如图所示

方案不唯一

数据范围

• 对于 10% 的数据：$n = 4$
• 对于 25% 的数据： $n ≤ 15$
• 对于另外 5% 的数据： 保证只有一个顶点上的水果为草莓；
• 对于 70% 的数据：$n ≤ 10^3$
• 对于 100% 的数据： $4 ≤ n ≤ 5 × 10^5 ， a_i$ = 1,2,3

【 校验器】

为了方便选手测试， 在 cake 目录下我们下发了Linux系统可执行文件 checker（ 无后缀名） 。

选手可以将输入文件（ 文件名必须是 cake.in） 和输出文件（ 文件名必须是 cake.out）与该可执行文件位于同一目录下， 在对应窗口空白处右键“ 在终端打开” ， 在出现的终端中输入“ ./checker” ， 运行后会将结果反馈给选手。

反馈的结果有以下可能：

• Correct： 答案正确；
• Wrong Answer： 答案错误（ 答案不合题意等） ；
• Invalid Format： 格式不合法（ 输入不合法、 输入输出超出数据范围等） ；
• Not Found ’ cake.in/out’ ： 未找到输入/输出文件。

来源

2021 年合肥市青少年信息学科普日活动(初中组)