题目描述

一个 $n \times n$ 的棋盘由 $n^{2}$ 个格子组成。每个格子要么是空的，要么有一个按钮。一开始，所有的按钮都是未激活的。现在要求激活一些按钮（至少一个），使得每一行和每一列的激活按钮的个数的奇偶性相同。

形式化地说，对于 $1\leq i \leq n$，令 $R_{i}$ 表示第 $i$ 行的激活按钮的个数，$C_{i}$ 表示第 $i$ 列的激活按钮的个数，那么所有的 $R_{1}, R_{2}, \ldots, R_{n}, C_{1}, C_{2}, \ldots, C_{n}$ 都必须对 $2$ 取余得到相同的结果。

---

输入格式

第一行包含两个整数 $n, m$（$1 \leq n \leq 10^5$，$1 \leq m \leq \min (n^{2}, 5\cdot 10^5)$），表示棋盘的大小和按钮的个数。

接下来的 $m$ 行描述了按钮的位置：第 $i$ 行包含两个整数 $r_{i}$ 和 $c_{i}$（$1 \leq r_{i}, c_{i} \leq n$），表示编号为 $i$（$1\leq i \leq m$）的按钮位于第 $r_{i}$ 行和第 $c_{i}$ 列的交叉处。
每个格子上最多有一个按钮。

---

输出格式

如果无法按照题目要求激活按钮，那么输出一行一个字符串 NIE。

否则：

• 第一行输出一个字符串 TAK。
• 第二行输出一个整数 $k$（$1 \leq k \leq m$），表示某个可行解中激活的按钮的个数。
• 第三行输出 $k$ 个两两不同的整数，表示激活的按钮的编号。这些编号可以按任意顺序输出。

---

样例 1

输入

3 6
1 1
1 2
2 2
3 1
3 2
3 3

输出

TAK
4
1 2 4 5

解释
我们有 $R_{1}=2, R_{2}=0, R_{3}=2, C_{1}=C_{2}=2, C_{3}=0$。

---

样例 2

见附加文件下 prz1ocen.in 和 prz1ocen.out。
该样例满足 $n=9, m=1, r_{1}=c_{1}=1$；答案是 NIE。

样例 3

见附加文件下 prz2ocen.in 和 prz2ocen.out。
该样例满足 $n=9, m=81$；答案是 TAK，可以激活所有的按钮。

样例 4

见附加文件下 prz3ocen.in 和 prz3ocen.out。
该样例满足 $n=10^{5}, m=5 \cdot 10^{5}$，按钮在前 $5$ 行；答案是 TAK。

---

数据范围与提示

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

子任务编号	附加限制	分值
1	$m \leq 20$	24
2	如果存在解，那么存在一个使得所有 $R_{i}, C_{i}$ 都是偶数的解
3	如果存在解，那么存在一个使得所有 $R_{i}, C_{i}$ 都是奇数的解
4	无附加限制	28

评分说明：
如果测试的答案不是 NIE，而你的程序只正确输出了第一行（TAK），那么你将获得该测试点 $50\%$ 的分数。特别地，为了获得这 $50\%$ 的分数，你不需要输出后面的行。