题目描述

题目译自 XXXI Olimpiada Informatyczna – I etap Przyciski

一个 $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))$，表示棋盘的大小和按钮的个数。按钮从 $1$ 到 $m$ 编号。接下来的 $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$ 个两两不同的整数，表示激活的按钮的编号。这些编号可以按任意顺序输出。

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](file:prz1ocen.in) 和 [prz1ocen.out](file:prz1ocen.out)。

该样例满足 $n=9, m=1, r_{1}=c_{1}=1$；答案是 NIE；

样例 3

见附加文件下 [prz2ocen.in](file:prz2ocen.in) 和 [prz2ocen.out](file:prz2ocen.out)。

该样例满足 $n=9, m=81$；答案是 TAK，可以激活所有的按钮。

样例 4

见附加文件下 [prz3ocen.in](file:prz3ocen.in) 和 [prz3ocen.out](file:prz3ocen.out)。

该样例满足 $n=10^{5}, m=5 \cdot 10^{5}$，按钮在前 $5$ 行；答案是 TAK。

数据范围与提示

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

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

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