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

#define MAXSIZE 20

/* Struktura pro hranu */
struct edge {
  int to;	/* Cílovy vrchol hrany */
  char inmatch;	/* Je hrana v párování? */
};

int m, n;			/* Rozměry plochy */
int map[MAXSIZE][MAXSIZE];	/* Mapa plochy */
int V[2];			/* Počty vrcholů v jednotlivých partitách */
struct edge E[MAXSIZE*MAXSIZE][4];	/* Hrany */
int Deg[MAXSIZE*MAXSIZE];	/* Stupně jednotlivých vrcholů */
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};	/* Jednotlivé směry */
int From[MAXSIZE*MAXSIZE];	/* Pole s vrcholy, odkud jsme přišli */

void ReadArea(void)
{
  int i, j;

  printf("Velikost plochy: ");
  scanf("%d %d", &m, &n);
  getchar();
  for (i = 0; i < m; i++) {
    printf("Radek %d:\n", i+1);
    for (j = 0; j < n; j++) {
      if (getchar() == '1') {	/* Místo k vydláždění? */
        V[(i+j)&1]++;	/* Máme nový vrchol do partity */
        map[i][j] = V[0] + V[1];	/* Poznamenáme si číslo vrcholu */
      }
    }
    getchar();
  }
}

/* Propojí jednotlivé vrcholy hranami */
void CreateGraph(void)
{
  int i, j, k;

  for (i = 0; i < m; i++)
   for (j = 0; j < n; j++)
     if (map[i][j])
       for (k = 0; k < 4; k++)
         /* Nevylézáme z mapy a je políčko volné? */
         if (i+dy[k] >= 0 && i+dy[k] < m && j+dx[k] >= 0 && j+dx[k] < n &&
             map[i+dy[k]][j+dx[k]])
           /* Přidáme hranu */
           E[map[i][j]][Deg[map[i][j]]++].to = map[i+dy[k]][j+dx[k]];	
}

/* Zjistí, zda je vrchol v párování */
int InMatching(int V)
{
  int k;

  for (k = 0; k < Deg[V]; k++)
    if (E[V][k].inmatch)
      return k;
  return -1;
}

/* Vrátí index hrany U<->V v U */
int EdgeIndex(int U, int V)
{
  int k;

  for (k = 0; k < Deg[U] && E[U][k].to != V; k++);
  return k;
}

/* Zamění hrany v párování a mimo něj na cestě */
void AlternateWay(int V)
{
  int inmatch = 1;
  
  while (From[V]) {
    E[V][EdgeIndex(V, From[V])].inmatch = inmatch;
    E[From[V]][EdgeIndex(From[V], V)].inmatch = inmatch;
    V = From[V];
    inmatch = !inmatch;
  }
}

/* Zjistí, zda existuje perfektní párování */
int PerfectMatching(void)
{
  int i, k;
  int Q[MAXSIZE*MAXSIZE];	/* Fronta s vrcholy ke zpracování */
  int QS, QE;			/* Počátek a konec fronty */
  int MatchSize;
  int AV;

  for (MatchSize = 0; MatchSize < V[0]; MatchSize++) {
    memset(From, 0, sizeof(int) * MAXSIZE * MAXSIZE);
    for (i = 1; i < V[0] + V[1]; i++)
      if (InMatching(i) == -1)	/* Vrchol je nespárovaný? */
        break;
    QS = QE = 0;
    for (Q[QE++] = i; QE > QS; QS++) {	/* Je něco ve frontě? */
      AV = Q[QS];
      for(k = 0; k < Deg[AV]; k++)
        if (!From[E[AV][k].to]) {	/* Ještě nedosažený vrchol? */
          From[E[AV][k].to] = AV;
          /* Je i soused nespárovaný? */
          if (InMatching(E[AV][k].to) == -1) {
            AlternateWay(E[AV][k].to);
            goto cont;			/* Začneme hledat další cesty */
          }
          /* Pridame do fronty vrchol z konce sparovane hrany */
          Q[QE] = E[E[AV][k].to][InMatching(E[AV][k].to)].to;
          From[Q[QE++]] = E[AV][k].to;
        }
    }
    /* Nenalezli jsme žádnou zlepšující cestu - vydláždění neexistuje */
    return 0;
cont:
  }
  return 1;
}

int main(void)
{
  ReadArea();		/* Načteme popis plochy */
  if (V[0] != V[1]) {	/* Různý počet vrcholů v partitách - párování neexistuje */
    puts("Tak tohle tedy nevydlazdite.");
    return 0;
  }
  CreateGraph();	/* Propojí jednotlivé vrcholy hranami */

  if (PerfectMatching())	/* Zjistí, zda existuje perf. párování */
    puts("Plocha vydlazit lze.");
  else
    puts("Plocha vydlazdit nelze.");
  return 0;
}