f = File.open("input.txt","r")
(nv, ne, m)=f.readline.split
nv=nv.to_i  # кількість вершин
ne=ne.to_i  # кількість ребер
b=[]        # списки суміжності
for k in 0...nv
  b[k]=[]
end
for l in 0...ne
  (j, k)=f.readline.split
  j=j.to_i
  k=k.to_i
  b[j].push(k)
  b[k].push(j)
end
f.close
l=[0]*nv # значення фнкції L
q=[0]    # список вершин у порядку досягнення
j=0      # поточний номер вершини у списку q
m=0      # номер останньої досягнутої вершини у списку q

while (j<=m) do
  for k in 0...b[q[j]].length
    x=b[q[j]][k]
    if ((x!=0) && (l[x]==0))
      m+=1
      q.push(x)
      l[x]=l[q[j]]+1
    end
  end
  j+=1
end

f = File.open("output.txt","w")
f.write l[0]
for j in 1...nv
  f.write " #{l[j]}"
end
f.write "\n"
f.close()