#include<cstdio>
using namespace std;
int main()
{
    int z;
    scanf("%d\n", &z);
    while(z--)
    {

              short n, m, u, v;
              bool graf[16][16] = {0}; //graf[][] - macierz sasiedztwa
              scanf("%hd %hd", &n, &m); // n - liczba wiercholkow nie liczac 0-wego, 3<=n<=15, m - liczba krawedzi 1<=m<=100
              while(m--)
              {
                        scanf("%hd %hd", &u, &v);
                        graf[v][u] = true;
                        graf[u][v] = true; //dziki temu nie musimy odwolujac sie do tabeli szukc wiekszego z indeksow, bo pola symetryczne wzgledem przekatnej [i][i] sa symetryczne
             }
              bool sciezka[65536][16] = {0};//0 - 65535 - maska bitowa podzbioru ktory rozwazamy,  - 15 - wiercholki grafu
              sciezka [1][0] = true; //1 - maska bitowa zbioru {0} - w tym zbiorze jest oczywiscie sciezka hamiltona
              int A; //A - maska bitowa podzbiru, u,v - wiercholki grafu
              for (A = 1; A < (1 << (n+1)); A++) // najwieksza maska bitowa to 2^(n+1) - 1
              {
                  for (u=0; u<=n; u++) //kazdy wierzcholek grafu oprocz 0
                  {
                      for (v=0; v<=n; v++)
                      {
  /**/                    if (graf[v][u]   &&   ((1<<v)&A) > 0 && ((1<<u)&A) > 0//v i u naleza do A
                                               &&   sciezka[A^(1<<u)][v]) //sciezka > 0 czyli istenieje sciezka hamiltona w A\{u} do wierzcholka v, w szczegolnosci jesli A\{u} nie zawiera {0}, to sciezka[][] == 0 i wpisac w nwe pole tez powinnismy 0
                          sciezka[A][u] = true;
                       }
                  }
              }
              //teraz dla A == 2^(n+1) - 1, czyli maski bitowej calego grafu sciezka[A][u] == true <==> istnieje sciezka hamiltona w calym grafie, zaczynajaca
              //sie w 0; czyli jezeli dla jakiegokolwiek wierzcholka u : sciezka[A][u] == true istnieje krawedz (O,u) to mamy cykl hamiltona
              bool czy_wypisalismy_tak = 0;
              A = (1 << (n+1)) - 1; //maska bitowa calego grafu (lacznie z 0 oczywiscie)
              for (u=1; u<=n; u++)
              {
                  if (sciezka[A][u]    &&    graf[u][0])
                  {
                                    printf("TAK\n");
                                    czy_wypisalismy_tak = 1;
                                    break;
                  }
              }
              if (!czy_wypisalismy_tak) printf("NIE\n");

    }
return 0;
}