program MinColor_Proba;
{$APPTYPE CONSOLE}
const
  n =  4 ;
  { Второй тест }
  {
    n =  8 ;
  }
  k =  4 ; { Мвксимальное число цветов в который надо раскрасить граф }
  {
  Второй тест
  k= 3 
  }
type
  mx = array[ 1  .. n,  1  .. n] of integer;
  colors = array[ 1  .. n] of integer;

const
  C: mx =
  (
    ( 0 ,  1 ,  1 ,  1 ), ( 1 ,  0 ,  1 ,  0 ), ( 1 ,  1 ,  0 ,  1 ), ( 1 ,  0 ,  1 ,  0 )
  );


  {  Второй тест
  (
    ( 0 ,  1 ,  1 ,  0 ,  0 ,  0 ,  0 ,  1 ),
    ( 1 ,  0 ,  1 ,  0 ,  0 ,  0 ,  0 ,  0 ),
    ( 1 ,  1 ,  0 ,  1 ,  0 ,  0 ,  0 ,  1 ),
    ( 0 ,  0 ,  1 ,  0 ,  1 ,  0 ,  0 ,  0 ),
    ( 0 ,  0 ,  0 ,  1 ,  0 ,  0 ,  0 ,  1 ),
    ( 0 ,  0 ,  0 ,  0 ,  0 ,  0 ,  1 ,  1 ),
    ( 0 ,  0 ,  0 ,  0 ,  0 ,  1 ,  0 ,  1 ),
    ( 1 ,  0 ,  1 ,  0 ,  1 ,  1 ,  1 ,  0 )
  );

  }


var
  color: colors;
  i: integer;

procedure bt(m: integer);
var
  i, j: integer;
  cont: boolean;
begin
  if m > n then writeln('finished')
  else begin
    for i :=  1  to k do begin
      color[m] := i;
      cont := true;
      for j :=  1  to n do begin
        if (C[j, m] =  1 ) and (color[j] = i) then cont := false;
      end;

      if cont then begin
        bt(m +  1 ); exit;
      end;
    end;
  end;
end;

begin
  bt( 1 );
  for i :=  1  to n do begin
    writeln('#', i: 2 , ' : color = ', color[i]);
  end;
  readln
end.