Manhunt

As is well known, Byteotia has $n$ cities connected by $m$ two-way roads. In this task the roads serve not only law-abiding citizens but also a dangerous criminal.

For some time a manhunt has been underway in Byteotia to bring the criminal to justice. For now, however, the scoundrel still enjoys his undeserved freedom. He spends each day hidden in one of the cities, and during the night he secretly slips along one of the $m$ roads to a neighboring city. He never stays in the same city on two consecutive days.

Right now nothing is known about his whereabouts. Into action steps Lieutenant Bytewicz, who has cracked far tougher cases than this. During a day he can comb through one city and will easily seize the villain, provided the villain happens to be in that very city. At night, using a helicopter, he can move to any other city. The manhunt is made harder by the fact that the criminal knows in advance exactly which city the Lieutenant will search on each day, so he has resolved to slip away for as long as he possibly can.

Does Lieutenant Bytewicz stand a chance of catching the criminal? More precisely, is there a strategy for the Lieutenant that guarantees a capture? If so, how few days at minimum does he need to achieve it?

The first line of input contains a single integer $t$ ($1 \le t \le 15$), the number of test cases, which are then described one after another.

The description of one test case begins with two integers $n$ and $m$ ($1 \le n \le 75\,000$, $0 \le m \le 75\,000$), the number of cities and the number of roads connecting them. Cities are numbered from $1$ to $n$. Each of the next $m$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i < b_i \le n$), meaning that cities $a_i$ and $b_i$ are joined by a two-way road. No pair of cities is joined by more than one direct road, and the road network makes it possible to travel from every city to every other city.

For each test case, the first line of output should contain the word TAK if a strategy that catches the criminal exists, or NIE otherwise. The second line should contain exactly one integer. If a strategy exists, this integer should equal the minimum number of days the Lieutenant needs to catch the bandit, assuming the criminal knows his moves in advance. Otherwise, the second line should contain the number $-1$.

Explanation for the third test case in the example: the Lieutenant can comb the cities numbered $2$, $4$, $4$, and $2$ in that order. Then the wrongdoer has no chance of escape.