# frozen_string_literal: true n = gets.to_i edges = Array.new(n + 1) { [] } (n - 1).times do x, y = gets.split.map(&:to_i) edges[x] << y edges[y] << x end zero_nodes = [1] + edges.each_with_index.drop(2) .find_all { |v, _i| v.length == 1 }.map(&:last) node_lengths = [nil] * (n + 1) checked_nodes = [false] * (n + 1) queue = [] next_queue = [] zero_nodes.each do |z| queue << z checked_nodes[z] = true node_lengths[z] = 0 end loop do i = queue.shift next_root_length = node_lengths[i] + 1 edges[i].each do |t| next if checked_nodes[t] next_queue << t checked_nodes[t] = true node_lengths[t] = next_root_length end next unless queue.empty? break if next_queue.empty? queue = next_queue next_queue = [] end node_lengths.shift puts node_lengths