D - Coloring Edges on Tree

2日かけてできませんでした〜〜〜〜！！！！泣

#問題
https://atcoder.jp/contests/abc146/tasks/abc146_d

#回答

N = gets.to_i
A,B = (N-1).times.map{gets.split.map(&:to_i)}.transpose
C=Array.new(N-1,0)
list=Array.new(N).map{Array.new}
for i in 0..N-2
  for j in 1..N
    if list[A[i]-1].include?(j)
      next
    end
    if list[B[i]-1].include?(j)
      next
    end
    list[A[i]-1].push(j)
    list[B[i]-1].push(j)
    C[i] = j
    break
  end
end
puts C.max,C

#結果

#感想
マジで悔しすぎて12時間以上考えたのに解けなくて泣いてる。

上のやり方だと、色を１から順に入れていくので、
1 2　→　1の色
4 5　→　1の色
3 4　→　頂点４で１の色を使っているので２の色
2 3　→　頂点２で１の色、頂点３で２の色を使っているので３の色
で３色必要になってしまうのだが、
実際は
1 2　→　1の色
4 5　→　2の色
3 4　→　1の色
2 3　→　2の色
で２色で良いので、ダメみたい、

なので、幅優先探索ってやつをやる必要があるみたいなのだが、
辺の場所などの保持が分からなくなって頭がパンクしました。おわり