Background

Translated from XXXI Olimpiada Informatyczna - Stage I Przyciski。

Problem Description

There is an $n \times n$ square grid with $m$ buttons inside.

You need to press some (at least one) buttons so that, for every row and every column, the parity of the number of pressed buttons is the same.

Input Format

The first line contains two positive integers $n, m$.

The next $m$ lines each contain two positive integers, representing the coordinates of a button.

Output Format

If there is no solution, output one line NIE.

If there is a solution, output TAK on the first line. On the second line output a positive integer $k$, the number of buttons you press. On the third line output several positive integers, the indices of the buttons you press.

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

TAK
4
1 2 4 5

9 1
1 1

NIE

见附件

TAK
4
1 2 10 11

见附件

TAK
4
1 2 100001 100002

Hint

Explanation for Sample 1: $R_1=2, R_2=0, R_3=2, C_1=C_2=2, C_3=0$.

Constraints: For all testdata, $1 \le n \le 100000$, $1 \le m \le \min(n^2, 500000)$.

If a solution exists and you correctly state that a solution exists but your construction is wrong, you can get $50\%$ of the score.

Translated by ChatGPT 5