P7202 [COCI 2019/2020 #1] Trobojnica

> "Everything will be in flames once red, white, and blue start running through your veins." - Slaven Bilić. In this task, we will study some polygons with $N$ colored sides (there are three colors in total). The vertices are numbered clockwise from $1$ to $N$. Your task is to find a triangulation of the polygon, i.e., split the polygon into $N-2$ triangles along diagonals, such that for every triangle in the triangulation, its three adjacent sides have three different colors, one of each color.

The first line contains the integer $N$ as described in the statement. The second line is an integer with exactly $N$ digits, describing the colors of the polygon sides. The first digit is the color of side $(1,2)$, the second digit is the color of side $(2,3)$, and so on. The $N$-th digit is the color of side $(N,1)$. Each digit will be one of $1,2,3$.

If there is no valid triangulation, output `NE` and terminate. Otherwise, output `DA` on the first line, and then output each diagonal used in the triangulation together with its color on the next $N-3$ lines. Each line should be in the format `X Y C`, where $X,Y$ are the two endpoints of the diagonal and $C$ is its color index ($1 \le X,Y \le N, 1 \le C \le 3$). The order of $X$ and $Y$ does not matter. If there are multiple valid triangulations, output any one of them.

#### Constraints | Subtask | Points | Constraints | | :----------: | :----------: | :----------: | | $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$ | #### Notes **The scoring for this problem follows the original COCI problem settings, with a full score of $110$.** This problem uses an unofficial [Special Judge](https://www.luogu.com.cn/paste/wxx1bxs2). You are welcome to hack (you may send a private message or post directly). **Translated from [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #1](https://hsin.hr/coci/archive/2019_2020/contest1_tasks.pdf) _T4 Trobojnica_.** Translated by ChatGPT 5