VCOLDWAT - Nước lạnh
Tác giả: flashmt
Ngôn ngữ: Pascal
const max=100000;
var n,m:longint;
a:array[0..max,0..2] of longint;
d,q:array[1..max] of longint;
procedure rf;
var i:longint;
begin
readln(n,m);
for i:=1 to m do readln(a[i,0],a[i,1],a[i,2]);
end;
procedure sort(l,r:longint);
var i,j,x:longint;
begin
i:=l; j:=r; x:=a[(i+j) div 2,0];
repeat
while a[i,0]<x do i:=i+1;
while x<a[j,0] do j:=j-1;
if i<=j then
begin
a[0]:=a[i]; a[i]:=a[j]; a[j]:=a[0];
i:=i+1; j:=j-1;
end;
until i>j;
if i<r then sort(i,r);
if j>l then sort(l,j);
end;
function bs(p:longint):longint;
var l,r,mid:longint;
begin
l:=1; r:=m;
repeat
mid:=(l+r) div 2;
if a[mid,0]=p then break
else
begin
if a[mid,0]<p then l:=mid+1
else r:=mid-1;
end;
until l>r;
if l>r then bs:=0
else bs:=mid;
end;
procedure pr;
var i,j,num,c,t:longint;
begin
sort(1,m);
fillchar(d,sizeof(d),0);
d[1]:=1;
i:=a[1,1]; j:=a[1,2];
d[i]:=2; d[j]:=2;
q[1]:=i; q[2]:=j;
num:=2; c:=1;
repeat
t:=bs(q[c]);
if t>0 then
begin
q[num+1]:=a[t,1]; q[num+2]:=a[t,2];
d[a[t,1]]:=d[q[c]]+1;
d[a[t,2]]:=d[a[t,1]];
num:=num+2;
end;
inc(c);
until (c>num) or (num=n-1);
end;
procedure wf;
var i:longint;
begin
for i:=1 to n do writeln(d[i]);
end;
begin
rf;
pr;
wf;
end.