P9923 [POI 2023/2024 R1] Buttons

Translated from [XXXI Olimpiada Informatyczna - Stage I](https://sio2.mimuw.edu.pl/c/oi31-1/dashboard/) [Przyciski](https://sio2.mimuw.edu.pl/c/oi31-1/p/prz/)。

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.

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

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.

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)$. | Subtask ID | Additional Constraints | Score | | :----------: | :----------: | :----------: | | 1 | $m \le 20$ | 24 | | 2 | If there is a solution, it is guaranteed that an even-size solution exists. | 24 | | 3 | If there is a solution, it is guaranteed that an odd-size solution exists. | 24 | | 4 | | 28 | 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