C-algae

C-algae is the Byteotians' favourite dish of their national cuisine. A c-algae has a very specific structure, defined recursively.

• A single cell is a c-algae.
• Two c-algae $K_1$ and $K_2$ can be combined into a new c-algae $K$ in exactly one of the two following ways:

  1. Disjoint union — take all cells and all connections of both $K_1$ and $K_2$.

     

  2. Join — take all cells and all connections of both $K_1$ and $K_2$, and in addition connect every cell of $K_1$ to every cell of $K_2$.

     

Recently the hostile country of Bitotia started selling algae that imitate c-algae so closely that a fake is hard to tell apart from a genuine c-algae. The Byteotian government has therefore asked you to write a program that verifies whether a given algae is really a c-algae.

Write a program that reads the descriptions of several algae from standard input, determines which of them are proper c-algae, and writes the answers to standard output. Every connection is undirected.

The first line contains a single integer $k$ ($1 \le k \le 10$) — the number of algae to examine. The descriptions of the $k$ algae follow.

Each description begins with a line containing two integers $n$ and $m$ ($1 \le n \le 10\,000$, $0 \le m \le 100\,000$) — the number of cells and the number of connections. The cells are numbered from $1$ to $n$. Each of the next $m$ lines contains two integers $a$ and $b$ ($a \ne b$, $1 \le a, b \le n$) describing an undirected connection between cells $a$ and $b$. Each connection is given exactly once.

Output $k$ lines. In the $i$-th line print:

• TAK if the $i$-th algae is a proper c-algae,
• NIE otherwise.