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

typedef unsigned mbool;
#define true 1
#define false 0

struct vertex;

#define OUTER 1
#define OUTER_CYCLE 2

struct edge
{
  struct vertex *v[2];
  struct edge *next[2];
  unsigned outer;
  mbool removed;
};

struct vertex
{
  unsigned id;
  unsigned degree;
  mbool small;
  struct vertex *next_small;
  struct edge *nbrs;
};

struct hash
{
  unsigned size;
  struct edge *entries[1];
};

struct graph
{
  unsigned n_vertices;
  unsigned n_edges;
  struct vertex *vertices;
  struct hash *edges;
};

static unsigned const primes[] =
{
  7,
  13,
  31,
  61,
  127,
  251,
  509,
  1021,
  2039,
  4093,
  8191,
  16381,
  32749,
  65521,
  131071,
  262139,
  524287,
  1048573
};

static unsigned
larger_prime (unsigned x)
{
  unsigned i;

  for (i = 0; primes[i] < x; i++)
    continue;

  return primes[i];
}

static struct hash *
new_hash (unsigned n_elem)
{
  unsigned size = larger_prime (5 * n_elem);
  struct hash *ret = (struct hash *) malloc (sizeof (struct hash) + (size - 1) * sizeof (struct edge *));

  ret->size = size;
  memset (ret->entries, 0, size * sizeof (struct edge *));
  return ret;
}

static unsigned
hash_fn (unsigned n1, unsigned n2)
{
  return 10007 * n1 + n2;
}

static void
hash_add (struct hash *hash, struct edge *e)
{
  unsigned from = hash_fn (e->v[0]->id, e->v[1]->id) % hash->size;

  while (hash->entries[from])
    {
      from++;
      if (from == hash->size)
	from = 0;
    }

  hash->entries[from] = e;
}

static struct edge *
hash_find (struct hash *hash, struct vertex *v[2])
{
  unsigned from = hash_fn (v[0]->id, v[1]->id) % hash->size;

  while (hash->entries[from])
    {
      if (hash->entries[from]->v[0] == v[0]
	  && hash->entries[from]->v[1] == v[1])
	return hash->entries[from];

      from++;
      if (from == hash->size)
	from = 0;
    }

  return NULL;
}

static void
free_hash (struct hash *hash)
{
  unsigned i;

  for (i = 0; i < hash->size; i++)
    if (hash->entries[i])
      free (hash->entries[i]);

  free (hash);
}

static struct edge *
add_edge (struct graph *g, unsigned x, unsigned y)
{
  struct edge *e = (struct edge *) malloc (sizeof (struct edge));
  unsigned i;

  if (x > y)
    {
      e->v[0] = g->vertices + y;
      e->v[1] = g->vertices + x;
    }
  else
    {
      e->v[0] = g->vertices + x;
      e->v[1] = g->vertices + y;
    }

  e->outer = 0;
  e->removed = false;

  for (i = 0; i < 2; i++)
    {
      e->next[i] = e->v[i]->nbrs;
      e->v[i]->nbrs = e;
      e->v[i]->degree++;
    }

  hash_add (g->edges, e);
  return e;
}

static struct graph *
new_graph (unsigned n_vertices, unsigned n_edges)
{
  struct graph *g = (struct graph *) malloc (sizeof (struct graph));
  unsigned i;

  g->n_vertices = n_vertices;
  g->n_edges = n_edges;
  g->vertices = (struct vertex *) calloc (n_vertices, sizeof (struct vertex));
  for (i = 0; i < g->n_vertices; i++)
    g->vertices[i].id = i;
  g->edges = new_hash (n_edges);

  return g;
}

static void
free_graph (struct graph *g)
{
  free (g->vertices);
  free_hash (g->edges);
  free (g);
}

static struct graph *
load_graph (void)
{
  struct graph *ret;
  unsigned n_edges, i, x, y, n;

  scanf ("%d%d", &n, &n_edges);

  if (!n)
    return NULL;

  ret = new_graph (n, n_edges);
  for (i = 0; i < n_edges; i++)
    {
      scanf ("%d%d", &x, &y);
      add_edge (ret, x,y);
    }

  return ret;
}

static struct vertex *
edge_dest (struct vertex *from, struct edge *e)
{
  return e->v[0] == from ? e->v[1] : e->v[0];
}

static struct edge **
next_nbr_ptr (struct vertex *from, struct edge *e)
{
  return e->v[0] == from ? &e->next[0] : &e->next[1];
}

static struct edge *
next_nbr (struct vertex *from, struct edge *e)
{
  return *next_nbr_ptr (from, e);
}

static void
prune_removed_edges (struct vertex *v)
{
  struct edge **pos = &v->nbrs;

  while (*pos)
    {
      if ((*pos)->removed)
	*pos = next_nbr (v, *pos);
      else
	pos = next_nbr_ptr (v, *pos);
    }
}

static void
remove_edge (struct graph *g, struct edge *e,
	     struct vertex **small_vertices)
{
  unsigned i;
  struct vertex *v;

  e->removed = true;

  for (i = 0; i < 2; i++)
    {
      v = e->v[i];
      v->degree--;

      if (v->small || v->degree > 2)
	continue;

      v->small = true;
      v->next_small = *small_vertices;
      *small_vertices = v;
    }
}

static struct edge *
find_edge (struct graph *g, struct vertex *v1, struct vertex *v2)
{
  struct vertex *v[2];

  if (v1->id < v2->id)
    {
      v[0] = v1;
      v[1] = v2;
    }
  else
    {
      v[0] = v2;
      v[1] = v1;
    }

  return hash_find (g->edges, v);
}

static mbool
reduce_small_vertex (struct graph *g, struct vertex *v,
		     struct vertex **small_vertices)
{
  struct edge *e1, *e2, *f;
  struct vertex *v1, *v2;

  if (v->degree == 0)
    return true;

  prune_removed_edges (v);

  if (v->degree == 1)
    {
      remove_edge (g, v->nbrs, small_vertices);
      return true;
    }

  e1 = v->nbrs;
  v1 = edge_dest (v, e1);
  e2 = next_nbr (v, e1);
  v2 = edge_dest (v, e2);

  f = find_edge (g, v1, v2);

  if (f)
    {
      if (f->outer == OUTER_CYCLE
	  || e1->outer == OUTER_CYCLE
	  || e2->outer == OUTER_CYCLE)
	return false;
    }
  else
    f = add_edge (g, v1->id, v2->id);
  
  if (e1->outer == OUTER_CYCLE
      || e2->outer == OUTER_CYCLE
      || f->outer == OUTER)
    f->outer = OUTER_CYCLE;
  else
    f->outer = OUTER;

  remove_edge (g, e1, small_vertices);
  remove_edge (g, e2, small_vertices);

  return true;
}

static mbool
outerplanar_p (struct graph *g)
{
  unsigned i;
  struct vertex *small_vertices = NULL, *v;

  if (g->n_vertices < 4)
    return true;

  if (g->n_edges < 6)
    return true;

  if (g->n_edges > 2 * g->n_vertices - 3)
    return false;

  for (i = 0; i < g->n_vertices; i++)
    if (g->vertices[i].degree <= 2)
      {
	g->vertices[i].next_small = small_vertices;
	small_vertices = g->vertices + i;
	small_vertices->small = true;
      }

  while (small_vertices)
    {
      v = small_vertices;
      small_vertices = v->next_small;

      if (!reduce_small_vertex (g, v, &small_vertices))
	return false;
    }

  for (i = 0; i < g->n_vertices; i++)
    if (g->vertices[i].degree > 2)
      return false;

  return true;
}

int
main(void)
{
  struct graph *g;

  while (1)
    {
      g = load_graph ();
      if (!g)
  	return 0;

      if (outerplanar_p (g))
	printf ("Yes, village can be built\n");
      else
	printf ("No, village cannot be built\n");

      free_graph (g);
    }
}