CF1009F Dominant Indices

You are given a rooted undirected tree consisting of $ n $ vertices. Vertex $ 1 $ is the root. Let's denote a depth array of vertex $ x $ as an infinite sequence $ [d_{x, 0}, d_{x, 1}, d_{x, 2}, \dots] $ , where $ d_{x, i} $ is the number of vertices $ y $ such that both conditions hold: - $ x $ is an ancestor of $ y $ ; - the simple path from $ x $ to $ y $ traverses exactly $ i $ edges. The dominant index of a depth array of vertex $ x $ (or, shortly, the dominant index of vertex $ x $ ) is an index $ j $ such that: - for every $ k < j $ , $ d_{x, k} < d_{x, j} $ ; - for every $ k > j $ , $ d_{x, k} \le d_{x, j} $ . For every vertex in the tree calculate its dominant index.

The first line contains one integer $ n $ ( $ 1 \le n \le 10^6 $ ) — the number of vertices in a tree. Then $ n - 1 $ lines follow, each containing two integers $ x $ and $ y $ ( $ 1 \le x, y \le n $ , $ x \ne y $ ). This line denotes an edge of the tree. It is guaranteed that these edges form a tree.

Output $ n $ numbers. $ i $ -th number should be equal to the dominant index of vertex $ i $ .