N = gets.to_i
edges = {}
queue = {}

readlines.map { |l| edges[l.split] = 0 }

root, deg = edges.keys.flatten.group_by(&:itself).max_by { |_, v| v.size }
queue[root] = 0
deg = deg.size
colors = (1..deg).to_a

while queue.size <= N do
    checking = queue.select { |k, v| v == 0 }.keys
    
    checking.each do |c|
        reserved = edges.select { |k, v| k.include?(c) && v != 0 }.values
        options = colors - reserved
        
        neighbors = edges.select { |k, v| k.include?(c) && v == 0 }.keys
        
        if neighbors.size == 0
            queue[c] = 1
            next
        end
        
        neighbors.map do |n|
            queue[n.reject { |i| i == c }[0]] = 0
            edges[n] = options.shift
        end
        queue[c] = 1
    end
    
    break if queue.reject { |k, v| v == 1 }.size == 0
end

puts deg
puts edges.values