题目描述

"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$），不必考虑对角线顶点顺序。

如果有多种符合条件的分法，输出任意一种。

4
1212

DA
1 3 3

4
1213

NE

7
1223121

DA
1 3 3
3 5 1
5 7 3
7 3 2

提示

数据范围及约定

说明

本题分值按 COCI 原题设置，满分 $110$。

本题使用非官方的 Special Judge，欢迎大家 hack（可私信或直接发帖）。

题目译自 COCI2019-2020 CONTEST #1 T4 Trobojnica 。