#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int Matrix[15][15];
typedef int Vector[15];

int main (int argc, char **argv, char **envp);
int StraightChain (int links);
int min (int a, int b);
int Validate (void);

Matrix Links;
Vector mask;
int size, nextbit=0;

int main (int argc, char **argv, char **envp) {

  int a, b, ct=1;

 stdin = fopen ("chains.in","r");
 stdout = fopen ("chains.out","w");
 while (1) {
  scanf ("%d",&size);
  if (size==0) break;
  memset (Links,0,sizeof Links);
  memset (mask,0,sizeof mask);
  while (1) {
   scanf ("%d %d",&a,&b);
   if (a==-1) break;
   if (!Links[a-1][b-1]) {
    Links[a-1][b-1]=Links[b-1][a-1]=1;
   }
  }
  printf("Set %d: Minimum links to open is %d\n",ct++,StraightChain(0));
 }
 fclose (stdin);
 fclose (stdout);
 return EXIT_SUCCESS;
}

int StraightChain (int links) {

  int i, ct, len;

 len = Validate ();
 if (len != -1 && len<=links+1) return links;
 ct = size;
 i=nextbit;
 while (nextbit<size) {
  mask[nextbit++]=1;
  ct = min (ct, StraightChain (links+1));
  mask[nextbit-1]=0;
 }
 nextbit = i;
 return ct;
}

int min (int a, int b) {

 return a<b?a:b;
}

int Validate (void) {

  int i, j, k, m, tot=0, OK;
  Matrix branch={};
  Vector owner={};
  Vector cts={};

 for (i=0; i < size; i++) if (!mask[i])
  for (j=0; j< size; j++) if (!mask[j])
   cts[i] += Links[i][j];
 for (i=0; i < size; i++) if (!mask[i]&&cts[i]>2) return -1;
 for (i=0; i < size; i++) {owner[i] = i; branch[i][i]=1;}
 for (i=1; i < size; i++) if (!mask[i]) 
  for (j = 0; j < i; j++) if (!mask[j])
   if (Links[i][j]) {
    m = min (owner[i],owner[j]);
    for (k=0; k < size; k++) if (!mask[k]) {
     branch[m][k] = branch[owner[i]][k] || branch[owner[j]][k];
     if (branch[m][k]) owner[k] = m;
    }
   }
 for (i=0; i < size; i++) if (!mask[i] && owner[i]==i) {
  tot++;
  for (OK=j=0; j < size; j++) if (!mask[j]&&branch[i][j]&&cts[j]<2) {
   OK = 1; break;}
  if (!OK) return -1;
 }
 return tot;
}