An $n \times n$ board consists of $n^2$ cells. Each cell is either empty or contains a button. Initially, no buttons are active. You must now activate a certain number of buttons (at least one) such that the number of activated buttons in every row and every column of the board has the same parity. Formally, if $R_i$ is the number of activated buttons in the $i$-th row and $C_i$ is the number of activated buttons in the $i$-th column (for $1 \le i \le n$), then all numbers $R_1, R_2, \dots, R_n, C_1, C_2, \dots, C_n$ must have the same remainder when divided by 2.

Input

The first line of input contains two integers $n$ and $m$ ($1 \le n \le 100\,000$, $1 \le m \le \min(n^2, 500\,000)$), representing the size of the board and the number of buttons. The buttons are numbered from 1 to $m$. The next $m$ lines describe the buttons: the $i$-th line contains two integers $r_i$ and $c_i$ ($1 \le r_i, c_i \le n$), meaning that the button numbered $i$ (for $1 \le i \le m$) is located at the intersection of the $r_i$-th row and the $c_i$-th column of the board. Each button is located in a different cell.

Output

If it is impossible to activate buttons according to the problem conditions, output the single word NIE.

Otherwise, in the first line of output, print the word TAK. In the second line, print a single integer $k$ ($1 \le k \le m$) representing the number of activated buttons in a valid solution. In the third line, print a sequence of $k$ distinct integers representing the indices of the activated buttons. These numbers can be printed in any order.

Examples

Input 1

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

Output 1

TAK
4
1 2 4 5

Note 1

We have $R_1 = 2, R_2 = 0, R_3 = 2, C_1 = C_2 = 2, C_3 = 0$.

Subtasks

If the answer for a test is not NIE, and your program correctly prints only the first line of the output, it will receive 50% of the points for that test. In particular, to receive these 50% of points for a test, you do not need to print the subsequent lines.