Problem Description

Input Format

The first line contains an integer $k$, indicating there are $k$ test cases.

For each test case, it starts with two integers $n$ and $m$. Then follow $m$ lines, each containing two integers describing an edge.

Output Format

Output a total of $k$ lines. For each line, output one decision: if the graph is c-algae, output TAK; otherwise, output NIE.

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

TAK
NIE
TAK

Hint

For $100\%$ of the testdata, $1\le k\le10$, $1\le n\le10^4$, $0\le m\le10^5$.

Translated by ChatGPT 5