题目描述

有一个 $n \times n$ 的网格，一些格子上面有按钮。

你需要选择一些（至少一个）按钮激活，使得每行每列激活按钮的个数的奇偶性相同。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，每行两个整数 $x,y$，表示 $(x,y)$ 上有一个按钮。

其余没给出的格子上没有按钮，一个格子不会被给出多次。

输出格式

如果无解，输出 NIE。

否则，第一行输出 TAK，第二行输出一个整数 $k$ 表示你选择的按钮的数量，第三行输出 $k$ 个整数表示你选择的按钮的编号。

若有多组解，输出任意一组均可。

样例

样例输入 #1

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

样例输出 #1

TAK
4
1 2 4 5

样例输入 #2

9 1
1 1

样例输出 #2

NIE

数据范围与约定

对于所有数据，有：

• $1 \le n \le 10^5$
• $1 \le m \le \min(n^2,5 \times 10^5)$

子任务	特殊性质	分值
$1$	$m \le 20$	$25$
$2$	若有解，则存在每行每列均激活偶数个按钮的解
$3$	若有解，则存在每行每列均激活奇数个按钮的解
$4$	无

本题有部分分：

若答案是 NIE：

• 若你输出 NIE，则获得 $100\%$ 的分数。
• 若输出其它内容，则获得 $0\%$ 的分数。

若答案是 TAK：

• 若你输出 TAK，且构造方案正确，则获得 $100\%$ 的分数。
• 若你仅输出 TAK，则获得 $50\%$ 的分数。为了获得这 $50\%$ 的分数，你不需要输出后面两行。
• 若你输出 NIE，则获得 $0\%$ 的分数。

一个子任务的得分是所有测试点中的最小值。