1. #include<bits/stdc++.h>
2. using namespace std;
3. vector<int> g[1000007];
4. bool odwiedzone[1000007], cykliczny;
5. int t, n, m, a, b;
6. void dfs(int u, int z)
7. {
8.     odwiedzone[u] = true;
9.     for(int i=0; i<g[u].size(); i++)
10.         {
11.             int v = g[u][i];
12.             if(odwiedzone[v] == false)
13.             {
14.                 dfs(v, u);
15.             }
16.             else if(z!=v)
17.             {
18.                 cykliczny = true;
19.             }
20.         }
21. }
22.  
23. int main()
24. {
25.     cin >> t;
26.     while (t--)
27.         {
28.             cin >> n >> m;
29.             for(int i=0; i<m ; i++)
30.             {
31.                 cin >> a >> b;
32.                 g[a].push_back(b);
33.                 g[b].push_back(a);
34.             }
35.             for(int i=1; i<=n; i++)
36.             {
37.                 if(odwiedzone[i]==false)
38.                 {
39.                     dfs(i, -1);
40.                 }
41.             }
42.             if(cykliczny==true)
43.             {
44.                 cout << "TAK" << "\n";
45.             }
46.             else
47.             {
48.                 cout << "NIE" << "\n";
49.             }
50.         }
51.     return 0;
52. }
53.