P6677 [COCI 2019/2020 #2] Checker

> "...fool me once, shame on — shame on you. Fool me — you can't get fooled again." — W

有一种规则多边形 ，它们的 $n$ 边分别用某三种颜色之一着色，并且其顶点按顺时针顺序从 $1$ 到 $n$ 表示。 多边形的三角剖分是指将其面积分解为一组不重叠的三角形的操作，这些三角形的边可能是多边形的边或其内对角线上。当然，在此任务中，用于多边形三角剖分的每条对角线也用三种颜色之一着色。 如果每个三角形的 $n\space−\space2$ 个三角形的所有三个面都具有不同的颜色，则称这样的三角剖分是“非常好”的。 您的任务是确定给定的对角线多边形是否被三角剖分以及该三角剖分是否非常好。

输入数据共 $n$ 行。 第一行，一个正整数 $T$，表示这个数据对应的 Subtask 编号。 第二行，一个正整数 $n$，含义见 **题目描述** 部分。 第三行，一个 $n$ 位数正整数，这些数字代表多边形边的颜色。更准确地说，第一个数字代表边 $(1, 2)$ 的颜色，第二个数字代表边 $(2, 3)$ 的颜色，第 $i$ 个数字表示边 $(i, i+1)$ 的颜色，**特别的**，第 $n$ 个数字表示边 $(n, 1)$ 的颜色。颜色用数字 $1, 2, 3$ 表示。 接下来的 $n-3$ 行，每一行都包含对一个对角线的描述，格式为 `x y c`，其中 $x$ 和 $y$ 是多边形顶点，$c$ 是对角线的颜色。数据保证顶点 $x$ 和 $y$ 既不相等也不相邻。

输出数据共一行。 - 如果输入多边形没有正确三角剖分，则应输出 $\mathtt{neispravna \space triangulacija}$。 - 如果输入多边形有正确三角剖分，但三角剖分不是好的，则应输出 $\mathtt{neispravno \space bojenje}$。 - 否则，输出 $\mathtt{tocno}$。

#### 数据规模及约定 本题采用 **捆绑测试**。 | Subtask 编号 | Subtask 分数 | Subtask 数据规模及约定 | | :----------- | :----------- | :----------- | | $1$ | $12$ | $4 \le n \le 300$ | | $2$ | $17$ | $4 \le n \le 2000$ | | $3$ | $23$ | $4 \le n \le 2 \times 10^5$，数据保证输出为 $\mathtt{neispravna \space triangulacija}$ 或 $\mathtt{tocno}$ | | $4$ | $23$ | $4 \le n \le 2 \times 10^5$，数据保证输出为 $\mathtt{neispravno \space bojenje}$ 或 $\mathtt{tocno}$ | | $5$ | $35$ | $4 \le n \le 2 \times 10^5$ | **特别的**，对于 $100\%$ 的数据，$1\le T\le 5$。 #### 说明 **本题分值按 COCI 原题设置，满分 $110$。** **题目译自 [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #2](https://hsin.hr/coci/archive/2019_2020/contest2_tasks.pdf) *T3 Checker*。**