Minimize Subtree Range Sum

Given a rooted tree with \(n\) nodes (node 1 is the root), let \(T_i\) denote the subtree rooted at node \(i\). You are required to assign each node a unique positive integer \(v_i\) chosen from \(\{1,2,\dots,n\}\). Define the range for node \(i\) as

\[ R_i = \max_{j \in T_i} \{v_j\} - \min_{j \in T_i} \{v_j\}, \]

and let

\[ f = \sum_{i=1}^{n} R_i. \]

Your task is to output an assignment of weights to nodes that minimizes \(f\). It can be shown that if for every node \(i\), the values assigned to all nodes in \(T_i\) form a consecutive segment of integers, then \(f\) is minimized. One natural way to achieve this is by performing a DFS (Depth First Search) on the tree and assigning increasing numbers in the order of discovery.

inputFormat

The first line contains a single integer \(n\) (\(1 \le n \le 10^5\)) representing the number of nodes in the tree. The following \(n-1\) lines each contain two integers \(u\) and \(v\) indicating that there is an edge between nodes \(u\) and \(v\). The tree is rooted at node 1.

outputFormat

Output a single line containing \(n\) integers separated by spaces. The \(i\)th integer is the positive integer assigned to node \(i\) such that the value \(f=\sum_{i=1}^{n}(\max_{j\in T_i}{v_j}-\min_{j\in T_i}{v_j})\) is minimized.

sample

1

1