/*
 * @(#) msu98_b.c - Problem 'B' ("The jury") solution
 * of the ACM Programming Contest at the MSU in 1998.
 * (c) 1998 Ivan Maidanski <ivmai@chat.ru> http://ivmai.chat.ru
 * Freeware program source. All rights reserved.
 **
 * Language: ANSI C
 * Tested with: Borland C++ v3.1
 * Last modified: 1998-09-27 19:25:00 GMT+04:00
 */

/* Input data file: b.dat */

#include <stdio.h> /* FILE, fopen(), fscanf(), printf() */

int n,i,j,k,kk,bi,bp,p;
char a[100][100];

void calc(void)
{
 int i;
 for (i=0;i<n;i++)
  if (a[i][i]>0)
  {
   for (j=0;j<i;j++)
    if (!a[j][j] && a[i][j])
     break;
   if (j==i)
    break;
  }
 if (i<n)
 {
  a[i][i]=0;
  k++;
  calc();
  a[i][i]=-1;
  k--;
  calc();
  a[i][i]=1;
  p++;
 }
  else if (kk<k)
   kk=k;
}

int main()
{
 int cur,cnt;
 FILE *f=fopen("b.dat","rt");
 fscanf(f,"%*[^0-9]%d",&cnt);
 for (cur=1;cur<=cnt;cur++)
 {
  fscanf(f,"%*[^0-9]%d%*[^0-9]%d",&n,&k);
  for (i=0;i<n;i++)
   for (j=0;j<n;j++)
    a[i][j]=0;
  while (k--)
  {
   fscanf(f,"%*[^0-9]%d%*[^0-9]%d",&i,&j);
   if (i!=j)
    a[i][j]=a[j][i]=1;
  }
  for (k=0;;)
  {
   for (i=0;i<n;i++)
    if (!a[i][i])
     break;
   if (i==n)
    break;
   for (a[i][i]=1;i<n;i++)
    if (a[i][i]>0)
    {
     for (j=0;j<i;j++)
      if (!a[j][j] && a[i][j])
       break;
     if (j<i)
     {
      a[j][j]=1;
      i=j-1;
     }
      else while (++j<n)
       if (a[i][j])
        a[j][j]=1;
    }
   for (p=i=0;i<n;i++)
    p+=a[i][i]>0;
   if (p<=20)
   {
    kk=k;
    calc();
    for (i=0;i<n;i++)
     if (a[i][i]>0)
      a[i][i]=-1;
    k=kk;
   }
    else for (;;k++)
    {
     for (i=0,bp=n;i<n;i++)
      if (a[i][i]>0)
      {
       for (j=p=0;j<n;j++)
        p+=a[j][j]>0 && a[i][j];
       if (bp>--p)
        bp=p,bi=i;
      }
     if (bp==n)
      break;
     for (j=0;j<n;j++)
      if (a[bi][j])
       a[j][j]=-1;
    }
  }
  printf("===== %d\nMaximal number of people for jury is %d.\n",cur,k);
 }
 return 0;
}