P7202 [COCI 2019/2020 #1] Trobojnica

> "Everything will be in flames once red, white, and blue start running through your veins." - Slaven Bilić 在该任务中，我们将会研究一些多边形，它们具有 $N$ 条被涂成颜色的边（总共有三种颜色），而顶点的编号沿顺时针依次为 $1$ 至 $N$。 你的任务是找到一个多边形的三角形分割方式，即将一个多边形沿对角线分成 $N-2$ 个三角形，使得多边形的每个三角形的三条邻边都各分别为三种不同的颜色。

第一行包含一个题中所提的整数 $N$。 第二行是一个共有 $N$ 个数位的整数，表示该多边形各边的颜色。其第一位表示边 $(1,2)$ 的颜色，第二位表示边 $(2,3)$ 的颜色，以此类推，第 $N$ 位表示边 $(N,1)$ 的颜色。所有数位都将会是 $1,2,3$ 中的其中一个。

如果没有符合条件的分法，输出 `NE` 并结束整个程序。 否则，在第一行输出 `DA` 并在接下来的 $N-3$ 行中输出每一条被分割的对角线及其颜色。 每行输出格式为 `X Y C`。其中 $X,Y$ 为对角线的两个顶点，而 $C$ 为其颜色编号（$1 \le X,Y \le N, 1 \le C \le 3$），不必考虑对角线顶点顺序。 如果有多种符合条件的分法，输出任意一种。

#### 数据范围及约定 | Subtask | 分值 | 数据范围及约定 | | :----------: | :----------: | :----------: | | $1$ | $20$ | $4 \le N \le 11$ | | $2$ | $40$ | $4 \le N \le 10^3$ | | $3$ | $50$ | $4 \le N \le 2 \times 10^5$ | #### 说明 **本题分值按 COCI 原题设置，满分 $110$。** 本题使用非官方的 [Special Judge](https://www.luogu.com.cn/paste/wxx1bxs2)，欢迎大家 hack（可私信或直接发帖）。 **题目译自 [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #1](https://hsin.hr/coci/archive/2019_2020/contest1_tasks.pdf) _T4 Trobojnica_ 。**