AT_abc479_e [ABC479E] Cut and Add

頂点に $ 1,2,\dots,N $ の番号がついた $ N $ 頂点の木があります。ここで、 $ N $ は奇数です。 辺にも $ 1,2,\dots,N-1 $ の番号がついており、辺 $ i $ は頂点 $ A_i,B_i $ を結んでいます。 各頂点 $ i $ には変数 $ x_i $ が設定されており、はじめは全ての頂点 $ i $ について $ x_i=0 $ です。 これから、 $ i=1,2,\dots,N-1 $ について順に以下の操作を行います。 - まず、辺 $ i $ を取り除く。その結果、木は $ 2 $ つの連結成分に分かれる。 - 含まれる頂点の数がより多い連結成分に含まれる全ての頂点 $ v $ について、 $ x_v $ に $ i $ を加算する。 - なお、 $ N $ は奇数なので、含まれる頂点の数がより多い連結成分は一意に定まる。 - 最後に、辺 $ i $ を復元する。 全ての操作を行った後の、各頂点に設定された変数の値 $ x_1,x_2,\dots,x_N $ を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_{N-1} $ $ B_{N-1} $

最終的な各変数の値を、以下の形式で出力せよ。 > $ x_1 $ $ x_2 $ $ \dots $ $ x_N $

### Sample Explanation 1 - $ i=1 $ について、以下の操作が行われます。 - 辺 $ 1 $ を取り除くと、木は頂点 $ 2 $ からなる連結成分と頂点 $ 1,3,4,5 $ からなる連結成分とに分かれます。 - より大きいのは頂点 $ 1,3,4,5 $ からなる連結成分なので、これらに設定された変数すべてに対して $ 1 $ を加算します。 - その結果、各変数の値は $ (x_1,x_2,x_3,x_4,x_5)=(1,0,1,1,1) $ となります。 - 最後に、辺 $ 1 $ を復元します。 - $ i=2 $ について、以下の操作が行われます。 - 辺 $ 2 $ を取り除くと、木は頂点 $ 5 $ からなる連結成分と頂点 $ 1,2,3,4 $ からなる連結成分とに分かれます。 - より大きいのは頂点 $ 1,2,3,4 $ からなる連結成分なので、これらに設定された変数すべてに対して $ 2 $ を加算します。 - その結果、各変数の値は $ (x_1,x_2,x_3,x_4,x_5)=(3,2,3,3,1) $ となります。 - 最後に、辺 $ 2 $ を復元します。 - $ i=3 $ について、以下の操作が行われます。 - 辺 $ 3 $ を取り除くと、木は頂点 $ 2,4 $ からなる連結成分と頂点 $ 1,3,5 $ からなる連結成分とに分かれます。 - より大きいのは頂点 $ 1,3,5 $ からなる連結成分なので、これらに設定された変数すべてに対して $ 3 $ を加算します。 - その結果、各変数の値は $ (x_1,x_2,x_3,x_4,x_5)=(6,2,6,3,4) $ となります。 - 最後に、辺 $ 3 $ を復元します。 - $ i=4 $ について、以下の操作が行われます。 - 辺 $ 4 $ を取り除くと、木は頂点 $ 3 $ からなる連結成分と頂点 $ 1,2,4,5 $ からなる連結成分とに分かれます。 - より大きいのは頂点 $ 1,2,4,5 $ からなる連結成分なので、これらに設定された変数すべてに対して $ 4 $ を加算します。 - その結果、各変数の値は $ (x_1,x_2,x_3,x_4,x_5)=(10,6,6,7,8) $ となります。 - 最後に、辺 $ 4 $ を復元します。 最終的な各変数の値は $ (x_1,x_2,x_3,x_4,x_5)=(10,6,6,7,8) $ です。 ### Constraints - 入力は全て整数 - $ N $ は $ 3 \le N \le 2 \times 10^5 - 1 $ を満たす奇数 - $ 1 \le A_i < B_i \le N $ - 与えられるグラフは木である