题目描述

译自 COCI 2019/2020 Contest #1 T4「Trobojnica」

给出一个正多边形，顶点按顺序从 $1$ 到 $N$ 进行编号，且每条边都会染上三种颜色中的一种。

一个正多边形的三角剖分是将该正多边形分割成若干不重叠的三角形，且每个三角形的三条边均为多边形的边或对角线。当然，在本题中，每条用于三角剖分的对角线也要染上三种颜色中的一种。

你的任务是求出一种三角剖分方案，使得将多边形三角剖分并将对角线染色后，每个三角形的三条边颜色均不同。

输入格式

第一行包含一个整数 $N$。

第二行包含一个由 $N$ 个数字组成的字符串。第一个数字代表边 $(1,2)$ 的颜色，第二个数字代表边 $(2,3)$ 的颜色，以此类推，第 $N$ 个数字代表边 $(N,1)$ 的颜色。颜色始终用数字 $1,2,3$ 表示。

输出格式

如果不存在合法的三角剖分方案，输出 NE。

否则第一行输出 DA，接下来 $N-3$ 行输出你的剖分方案中用到的对角线。

每条对角线用三个整数 $X,Y,C$ 表示，其中 $X,Y$ 代表对角线的两个端点，$C$ 代表对角线的颜色。你的输出必须满足 $1 \leq X,Y \leq N, 1 \leq C \leq 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

数据范围与提示

评分标准

如果你第一行判断的结果正确，且给出了正确的剖分方案，则你将得到该测试点全部的分数。

否则，如果你第一行判断的结果正确，则你将得到该测试点 $10\%$ 的分数。

请注意，你在一个测试点上的得分，等于你在该测试点所有子任务的最低得分。

子任务

子任务 1（15 分）：$4 \leq N \leq 11$
子任务 2（35 分）：$4 \leq N \leq 10^3$
子任务 3（50 分）：$4 \leq N \leq 2 \times 10^5$