program nudlova_lhota;
const MAX=100;
var
  ruzny : array[1..MAX, 1..2] of word;
  rovny : array[1..MAX, 1..2] of word;
  spojeno : array[1..MAX] of word;
  n, mruz, mrov: word; { počet domů a počet snímků }

procedure nacti;
var
  i : word;
begin
  readln(n,mruz,mrov);
  for i := 1 to mruz do readln(ruzny[i, 1], ruzny[i, 2]);
  for i := 1 to mrov do readln(rovny[i, 1], rovny[i, 2]);
end;

procedure spoj;
var
  spojen_na : array[1..MAX] of word;
  spojit : array[1..MAX] of boolean;
  i, j : word;
begin
  for i := 1 to n do  
    spojit[i] := false;
  for i := 1 to mrov do
    if rovny[i, 1]+1=rovny[i, 2] then
      spojit[rovny[i, 2]] := true;
  j := 0;
  for i := 1 to n do
    if spojit[i] then begin
      spojen_na[i] := j;
      inc(spojeno[j]);
    end  
    else begin
      inc(j);
      spojen_na[i] := j;
      spojeno[j] := 1;
    end;
  n := j;	
  for i := 1 to mruz do begin
    ruzny[i, 1] := spojen_na[ruzny[i, 1]];
    ruzny[i, 2] := spojen_na[ruzny[i, 2]];
    if ruzny[i,1]=ruzny[i,2] then begin
      writeln('Domy nelze obarvit.');
      exit
    end
  end;	  
  j := 0;  
  for i := 1 to mrov do begin
    if rovny[i,2]-rovny[i,1]>spojen_na[rovny[i,2]]-spojen_na[rovny[i,1]] then
      continue;
    inc(j);
    rovny[j,1]:=spojen_na[rovny[i,1]];
    rovny[j,2]:=spojen_na[rovny[i,2]];
  end;
  mrov := j;  
end;

procedure spocitej;
var
  ruznost : array[1..MAX] of boolean;
  nejvetsi : array[1..MAX] of word;
  barev : array[1..MAX] of word;
  barva : array[1..MAX] of word;
  posledni : array[1..MAX] of word;
  i, j:word;
begin
  for i := 1 to n do 
    ruznost[i] := false;
  for i := 1 to mruz do
    if ruzny[i,1]+1=ruzny[i,2] then
      ruznost[ruzny[i,2]] := true;
  for i := 1 to n do 
    nejvetsi[i]:=0;	
  for i := 1 to mrov do
    if nejvetsi[rovny[i,2]]<rovny[i,1] then
      nejvetsi[rovny[i,2]]:=rovny[i,1];
  barev[1] := 1; barva[1] := 1; posledni[1] := 0;	
  barev[2] := 2; barva[2] := 2; posledni[2] := 0;	
  for i := 3 to n do
    if nejvetsi[i] <= posledni[i-1] then begin
      barev[i] := barev[i-1]+1;
      barva[i] := barev[i];
      posledni[i] := posledni[i-1];
    end
    else
      if ruznost[i] then begin
        barev[i] := barev[i-1];
        barva[i] := barva[i-2];
        posledni[i] := i-2;
      end
      else begin
        barev[i] := barev[i-1];
        barva[i] := barva[i-1];
        posledni[i] := i-1;
      end;
  writeln('Maximální počet barev: ', barev[n]);
  for i := 1 to n do
    for j := 1 to spojeno[i] do
      write(barva[i], ' ');
    writeln;  
end;

begin
  nacti;
  spoj;
  spocitej;
end.