题目背景

题目描述

一个 $n\times n$ 的方阵，里面有 $m$ 个按钮。

你需要按下若干个（至少一个）按钮，使得每行每列被按下的按钮个数奇偶性相同。

输入格式

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

接下来 $m$ 行，每行两个正整数，表示一个按钮的坐标。

输出格式

如果无解，输出一行 NIE。

如果有解，第一行输出 TAK，第二行输出一个正整数 $k$，表示按下按钮的个数，第三行输出若干个正整数，表示你按下的按钮的编号。

样例 #1

样例输入 #1

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

样例输出 #1

TAK
4
1 2 4 5

样例 #2

样例输入 #2

9 1
1 1

样例输出 #2

NIE

样例 #3

样例输入 #3

见附件

样例输出 #3

TAK
4
1 2 10 11

样例 #4

样例输入 #4

见附件

样例输出 #4

TAK
4
1 2 100001 100002

提示

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

对于所有的数据，$1\leq n\leq 100000$，$1\leq m\leq\min(n^2,500000)$。

子任务编号	附加限制	分值
1	$m\leq 20$	24
2	如果有解，保证存在偶数解
3	如果有解，保证存在奇数解
4		28

如果有解并且你指出有解但是构造错误，你能得到 $50\%$ 的分数。