#include <iostream>
#include <vector>
#include <stack>
#include <list>
using namespace std;
list <int> *graf;
int *color, *where_now;
bool cykl;
vector <int> topsort;

void dfs(int x){
      if(cykl == false){
              color[x] = 1;

              for(list<int>::iterator K = graf[x].begin(); K != graf[x].end(); K++){
                      if(color[*K] == 0){
                              dfs(*K);
                      }
                      else{
                              if(color[*K] == 1){
                                      cykl = true;
                                      return;
                              }
                      }
              }

              topsort.push_back(x);
              color[x] = 2;
      }
}

void dfsMAX(int V){
      cykl = false;

      topsort.clear();

      for(int i = 1; i <= V; i++){
              if(color[i] != 2){
                      dfs(i);
              }
              if(cykl == true)
                      break;
      }
}

int main(){
      ios_base::sync_with_stdio(false);

      int z;
      cin >> z;

      while(z--){
              int V, E;
              cin >> V >> E;

              graf = new list<int>[V + 1];
              color = new int[V + 1];
              where_now = new int[V + 1];

              for(int i = 1; i <= V; i++){
                      color[i] = 0;
                      where_now[i] = 0;
              }

              for(int i = 1; i <= E; i++){
                      int a, b; char c;
                      cin >> a >> c >> b;
                      graf[a].push_back(b);
              }
              dfsMAX(V);

              if(cykl == true){
                      cout << "NIE" << endl;
              }else{
                      where_now[topsort[topsort.size() - 1]] = 1;

                      int maks = 1;

                      for(list<int>::iterator K = graf[topsort[topsort.size() - 1]].begin(); K != graf[topsort[topsort.size() - 1]].end(); K++){
                              where_now[*K] = max(where_now[*K], where_now[topsort[topsort.size() - 1]] + 1);
                              maks = max(maks, where_now[*K]);
                      }

                      for(int i = topsort.size() - 2; i >= 0; i--){
                              if(where_now[topsort[i]] == 0){
                                      where_now[topsort[i]] = 1;
                              }

                              for(list<int>::iterator K = graf[topsort[i]].begin(); K != graf[topsort[i]].end(); K++){
                                      where_now[*K] = max(where_now[*K], where_now[topsort[i]] + 1);
                                      maks = max(maks, where_now[*K]);
                              }
                      }

                      vector <int> tab[maks + 1];

                      for(int i = topsort.size() - 1; i >= 0; i--){
                              tab[where_now[topsort[i]]].push_back(topsort[i]);
                      }

                      cout << "TAK " << maks << endl;
                      for(int i = 1; i <= maks; i++){
                              cout << tab[i].size() << " ";
                              for(int j = 0; j < (int)tab[i].size(); j++){
                                      cout << tab[i][j] << " ";
                              }

                              cout << endl;
                      }
              }
              for(int i = 1; i <= V; i++){
                      graf[i].clear();
              }

              delete [] graf;
              delete [] color;
              delete [] where_now;
      }
      return 0;
}