一个 $n \times n$ 的棋盘由 $n^2$ 个格子组成。每个格子要么是空的，要么上面有一个按钮。最初，没有任何按钮被激活。现在需要激活一定数量的按钮（至少一个），使得每一行和每一列中被激活的按钮数量具有相同的奇偶性。形式化地，如果 $R_i$ 是第 $i$ 行中被激活的按钮数量，$C_i$ 是第 $i$ 列中被激活的按钮数量（对于 $1 \le i \le n$），则所有数字 $R_1, R_2, \dots, R_n, C_1, C_2, \dots, C_n$ 对 $2$ 取模的余数必须相同。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 100\,000, 1 \le m \le \min(n^2, 500\,000)$)，分别表示棋盘的大小和按钮的数量。按钮编号从 $1$ 到 $m$。

接下来的 $m$ 行描述了这些按钮：第 $i$ 行包含两个整数 $r_i$ 和 $c_i$ ($1 \le r_i, c_i \le n$)，表示编号为 $i$ 的按钮（对于 $1 \le i \le m$）位于棋盘的第 $r_i$ 行和第 $c_i$ 列。

每个按钮位于不同的格子上。

输出格式

如果无法按照题目要求激活按钮，请输出一行 NIE。

否则，在第一行输出 TAK。在第二行输出一个整数 $k$ ($1 \le k \le m$)，表示在某个正确方案中被激活的按钮数量。在第三行输出 $k$ 个互不相同的整数，表示被激活的按钮编号。这些数字可以以任意顺序输出。

子任务

测试集分为以下子任务。每个子任务的测试用例由一组或多组独立的测试数据组成。

如果测试用例的答案不是 NIE，而你的程序仅正确输出了输出的第一行，则该测试用例将获得 50% 的分数。特别地，为了获得该测试用例 50% 的分数，不需要输出后续行。

样例

样例输入 1

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

样例输出 1

TAK
4
1 2 4 5

说明

样例解释：此时 $R_1 = 2, R_2 = 0, R_3 = 2, C_1 = C_2 = 2, C_3 = 0$。