Problem Description

A $n \times n$ matrix contains $m$ buttons.

You need to press several (at least one) buttons such that the parity (odd or even) of the number of pressed buttons in each row and each column is the same.

Input Format

The first line contains two positive integers $n$ and $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, the first line should output TAK, the second line should output a positive integer $k$ representing the number of buttons pressed, and the third line should output several positive integers representing the indices of the buttons you pressed.

Sample Input and Output

Sample Input #1

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

Sample Output #1

TAK
4
1 2 4 5

Sample Input #2

9 1
1 1

Sample Output #2

NIE

Sample Input #3

(Not provided in text)

Sample Output #3

TAK
4
1 2 10 11

Sample Input #4

(Not provided in text)

Sample Output #4

TAK
4
1 2 100001 100002

Notes

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

For all data, $1 \leq n \leq 100000$, $1 \leq m \leq \min(n^2, 500000)$.

If a solution exists and you indicate that a solution exists but the construction is incorrect, you will receive 50% of the score.

见题面 Input 部分

见题面 Output 部分