CF690C3 Brain Network (hard)

Breaking news from zombie neurology! It turns out that – contrary to previous beliefs – every zombie is born with a single brain, and only later it evolves into a complicated brain structure. In fact, whenever a zombie consumes a brain, a new brain appears in its nervous system and gets immediately connected to one of the already existing brains using a single brain connector. Researchers are now interested in monitoring the brain latency of a zombie. Your task is to write a program which, given a history of evolution of a zombie's nervous system, computes its brain latency at every stage.

The first line of the input contains one number $ n $ – the number of brains in the final nervous system ( $ 2

Output $ n-1 $ space-separated numbers – the brain latencies after the brain number $ k $ is added, for $ k=2,3,...,n $ .