CTREE - Tô màu nhỏ nhất
Tác giả: RR
Ngôn ngữ: Pascal
{$R+,Q+}
program CTREE;
const
FINP='';
FOUT='';
MAXN=10001;
var
father,xet,a,start,deg,dx,eu,ev:array[1..MAXN] of longint;
d:array[1..MAXN,1..3] of longint;
ke:array[1..MAXN*2] of longint;
kq,n:longint;
function min(a,b:longint):longint;
begin
if a<b then min:=a else min:=b;
end;
procedure inp;
var
f:text;
i,u,v:longint;
begin
assign(f,FINP); reset(f);
readln(f,n);
for i:=1 to n-1 do
begin
readln(f,u,v);
inc(deg[u]); inc(deg[v]);
eu[i]:=u; ev[i]:=v;
end;
close(f);
end;
procedure init;
var
i,u,v:longint;
begin
start[1]:=1;
for i:=2 to n+1 do start[i]:=start[i-1]+deg[i-1];
for i:=1 to n-1 do
begin
u:=eu[i]; v:=ev[i];
ke[start[u]+dx[u]]:=v;
ke[start[v]+dx[v]]:=u;
inc(dx[u]); inc(dx[v]);
end;
end;
procedure ans;
var
f:text;
i:longint;
begin
assign(f,FOUT); rewrite(f);
writeln(f,kq);
for i:=1 to n do
writeln(f,a[i]);
close(f);
end;
procedure DFS1(u:longint);
var
i,v,j:longint;
begin
xet[u]:=1;
d[u,1]:=1; d[u,2]:=2; d[u,3]:=3;
for i:=start[u] to start[u+1]-1 do
begin
v:=ke[i];
if xet[v]=1 then continue;
DFS1(v);
father[v]:=u;
d[u,1]:=d[u,1]+min(d[v,2],d[v,3]);
d[u,2]:=d[u,2]+min(d[v,1],d[v,3]);
d[u,3]:=d[u,3]+min(d[v,1],d[v,2]);
end;
end;
procedure DFS2(u:longint);
var
i,v:longint;
begin
xet[u]:=1;
for i:=start[u] to start[u+1]-1 do
begin
v:=ke[i];
if xet[v]=1 then continue;
case a[u] of
1: begin if d[v,2]<d[v,3] then a[v]:=2 else a[v]:=3; end;
2: begin if d[v,1]<d[v,3] then a[v]:=1 else a[v]:=3; end;
3: begin if d[v,1]<d[v,2] then a[v]:=1 else a[v]:=2; end;
end;
DFS2(v);
end;
end;
procedure solve;
begin
DFS1(1);
kq:=d[1,1]; a[1]:=1;
if d[1,2]<kq then begin kq:=d[1,2]; a[1]:=2; end;
if d[1,3]<kq then begin kq:=d[1,3]; a[1]:=3; end;
fillchar(xet,sizeof(xet),0);
DFS2(1);
end;
begin
inp;
init;
solve;
ans;
end.