Problem Description

You are given $n$ points and $m$ bidirectional edges. The task is to determine if it is possible to convert some of these edges into directed edges such that, considering only the directed edges, the in-degree of each point is exactly $1$.

Input Format

The first line contains two integers $n$ and $m$ ($1 \le n \le 100,000$, $1 \le m \le 200,000$), representing the number of points and edges, respectively. The next $m$ lines each contain two integers $a$ and $b$, indicating that there is a bidirectional edge between points $a$ and $b$. The input guarantees that there are no duplicate edges or self-loops.

Output Format

If there is no valid solution, output "NIE". Otherwise, output "TAK" on the first line, followed by $n$ lines where the $(i+1)$-th line specifies the point from which the in-degree of point $i$ is derived.

Task

Write a program that:

• reads the description of the Byteotian road system from the standard input,
• determines for each town on which road it should impose toll, or asserts that it is impossible,
• writes the result to the standard output.

Input Format

The first line of the standard input contains two integers: $n$ and $m$ ($1 \le n \le 100,000$, $1 \le m \le 200,000$), denoting the number of towns and roads in Byteotia, respectively. The towns are numbered from $1$ to $n$. The next $m$ lines describe the roads. Each line contains two integers $a_i$ and $b_i$, indicating that towns $a_i$ and $b_i$ are directly connected by a road.

Output Format

If it is impossible to collect the toll in accordance with the royal edict, your program should output the word "NIE" in the first and only line of the standard output. Otherwise, it should output the word "TAK" in the first line, followed by $n$ lines specifying which city collects toll from which road. The $(i+1)$-th line should indicate on which road the town number $i$ imposes toll. Since town number $i$ is obviously one endpoint of this road, it is sufficient to specify the other endpoint. Thus, if town number $i$ imposes toll on the road connecting it with town number $j$, the $(i+1)$-th line should contain the number $j$. If more than one solution exists, output any one of them.

Sample Input and Output

Sample Input #1

4 5
1 2
2 3
1 3
3 4
1 4

Sample Output #1

TAK
3
3
4
1

Sample Input #2

4 3
1 3
3 4
2 3

Sample Output #2

NIE

Notes

Sample 1:

Sample 2:

见题面 Input 部分

见题面 Output 部分