题目描述

题目译自 XXVI Olimpiada Informatyczna – III etap Remont

经过数周的辛劳，Bajtazar 几乎完成了新公寓的装修，只剩一面墙需粉刷。他将墙面分为 $n$ 个等宽的垂直条带，计划用 $k$ 种颜色（编号 $1$ 至 $k$）为每条带上色。在购物狂热中，他买了一套促销的双色滚筒，每个滚筒有左右两种颜色（可能相同），可一次为相邻两条带涂上对应颜色。套装包含 $k^2$ 个滚筒，覆盖所有颜色对，每对仅一个滚筒。但滚筒为一次性，只能涂一对相邻条带。

Bajtazar 已选定墙面颜色：条带依次为颜色 $a_1, a_2, \ldots, a_n$。同一条带可被多个滚筒涂刷，但颜色必须一致。你的任务是帮助 Bajtazar 判断他的配色方案是否可实现。

输入格式

第一行包含一个整数 $t$ $(1 \leq t \leq 10)$，表示测试数据组数。接下来是 $t$ 组测试数据的描述。

每组测试数据的第一行包含两个整数 $n, k$ $(1 \leq k \leq n, n \geq 2)$，分别表示条带数和颜色种类数。第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq k)$，表示各条带所需的颜色。

输出格式

输出 $t$ 行。对于第 $i$ $(1 \leq i \leq t)$ 组测试数据，若配色方案不可实现，输出 NIE；否则输出 TAK。

2
4 3
2 3 2 3
7 3
2 2 2 3 2 3 1

NIE
TAK

第一组测试数据答案为 NIE：要实现配色，Bajtazar 需两次使用颜色对 $(2,3)$ 的滚筒。第二组测试数据可实现，使用滚筒 $(2,2), (2,3), (3,2), (3,1)$。

附加样例

1. $t=8$，包含所有 $n=4, k=2$ 的可能配色情况。
2. $t=2$，两组测试中 $n=150000$。第一组测试中 $k=150000$，且对 $1 \leq i \leq n$，$a_i=i$；第二组测试中 $k=4$，且 $a_i=1$。答案分别为 TAK 和 NIE。

数据范围与提示

详细子任务附加限制及分值如下表所示。