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

#define MAX 112

void le(int amizades[][MAX], int m) {
  int i, j;
  int count;
  for (count = 0; count < m; count++) {
    scanf(" %d %d",&i,&j);
    amizades[i][j] = amizades[j][i] = 1;
  }
}

void separa(int amizades[][MAX], int n, int lado[], int v, int ladoAtual) {
  int ladoProx, i;

  lado[v] = ladoAtual;

  ladoProx = (-1)*ladoAtual;

  for (i = 0; i < n; i++) {
    if(amizades[v][i] && !lado[i]) {
      separa(amizades, n, lado, i, ladoProx);
    }
  }
}

int confere(int amizades[][MAX], int n, int lado[]) {
  int i, j;
  for (i = 0; i < n; i++) {
    for (j = 0; j < i; j++) {
      if ((amizades[i][j] && (lado[i] == lado[j])))  return 1;
    }
  }
  return 0;
}

int main() {
  int amizades[MAX][MAX], lado[MAX], m, n, ntest = 0;
  int i;

  while (scanf(" %d %d", &n, &m) != EOF) {
    memset(amizades, 0, sizeof(amizades));
    memset(lado, 0, sizeof(lado));
    le(amizades, m);

    for(i = 0; i < n; i++) {
      if(!lado[i]) separa(amizades, n, lado, i, -1);
    }

    if(ntest) putchar('\n');
    printf("Instancia %d\n",++ntest);
    if(confere(amizades,n,lado)) printf("nao\n");
    else printf("sim\n");

  }
  return 0;
}