Odd-Length Cycle

Given an undirected graph, determine whether it contains a cycle of odd length.

You are given a number $t$ of test cases, followed by $t$ graphs. For each graph, decide whether an odd-length cycle exists in it.

The first line contains the number of test cases $t$ ($1 \le t \le 100$). Then $t$ undirected graphs follow.

Each graph starts with two integers $n$ and $m$, the number of vertices and the number of edges ($1 \le n \le 10^5$, $1 \le m \le 2 \times 10^5$). Each of the next $m$ lines contains two integers between $1$ and $n$, the two endpoints of one edge.

For each graph, print the answer on its own line. Print TAK if the graph contains a cycle of odd length (equivalently, the graph is not bipartite), and NIE otherwise.