using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("3");
WillReturn.Add("1 2");
WillReturn.Add("2 3");
//3
//2
//3
}
else if (InputPattern == "Input2") {
WillReturn.Add("2");
WillReturn.Add("1 2");
//1
//1
}
else if (InputPattern == "Input3") {
WillReturn.Add("6");
WillReturn.Add("1 6");
WillReturn.Add("1 5");
WillReturn.Add("1 3");
WillReturn.Add("1 4");
WillReturn.Add("1 2");
//5
//9
//9
//9
//9
//9
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static long mN;
// 隣接リスト
static Dictionary<long, List<long>> mToNodeListDict = new Dictionary<long, List<long>>();
struct NodeInfo
{
internal long ChildNodeCnt;
internal long DistanceSum;
}
// 木DPとReRootingの設定01 配られてる値が無い時の値
static NodeInfo DeriveDefaultNodeVal()
{
NodeInfo DefaultNodeVal;
DefaultNodeVal.ChildNodeCnt = 1;
DefaultNodeVal.DistanceSum = 0;
return DefaultNodeVal;
}
// 木DPとReRootingの設定02 ノード値を引数として、配る値を返す
static NodeInfo DeriveSendVal(NodeInfo pNodeInfo)
{
NodeInfo Copied = pNodeInfo;
Copied.DistanceSum += Copied.ChildNodeCnt;
return Copied;
}
// 木DPとReRootingの設定03 ノード値と、配られた値を、引数とし、新しいノード値を返す
static NodeInfo DeriveNewNodeVal(NodeInfo pNodeVal, NodeInfo pSendVal)
{
pNodeVal.DistanceSum += pSendVal.DistanceSum;
pNodeVal.ChildNodeCnt += pSendVal.ChildNodeCnt;
return pNodeVal;
}
// 木DPとReRootingの設定04 配る値のListを引数として、最終的な配る値を返す
static NodeInfo DeriveMergedSendVal(List<NodeInfo> pSendValList)
{
NodeInfo SendVal = DeriveDefaultNodeVal();
foreach (NodeInfo EachSendVal in pSendValList) {
SendVal = DeriveNewNodeVal(SendVal, EachSendVal);
}
return SendVal;
}
static void Main()
{
List<string> InputList = GetInputList();
long[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();
mN = long.Parse(InputList[0]);
foreach (string EachStr in InputList.Skip(1)) {
SplitAct(EachStr);
long S = wkArr[0];
long T = wkArr[1];
if (mToNodeListDict.ContainsKey(S) == false) {
mToNodeListDict[S] = new List<long>();
}
if (mToNodeListDict.ContainsKey(T) == false) {
mToNodeListDict[T] = new List<long>();
}
mToNodeListDict[S].Add(T);
mToNodeListDict[T].Add(S);
}
// 前後に累積値を使うので、ノード番号の昇順にソート
foreach (var EachPair in mToNodeListDict) {
EachPair.Value.Sort();
}
// 状態[ノード]なDP表
var TreeDPDict = new Dictionary<long, NodeInfo>();
// 根から葉に向かってDFSしてノードのListを返す
List<JyoutaiDef1> DFSResult = ExecDFS1(1);
DFSResult.Reverse(); // 葉から根への順番にする
foreach (JyoutaiDef1 EachJyoutai in DFSResult) {
// 親ノードに配る木DP
int Node = EachJyoutai.CurrNode;
if (TreeDPDict.ContainsKey(Node) == false) {
TreeDPDict[Node] = DeriveDefaultNodeVal();
}
int ParentNode = EachJyoutai.ParentNode;
// 根ノードの場合
if (ParentNode == -1) continue;
if (TreeDPDict.ContainsKey(ParentNode) == false) {
TreeDPDict[ParentNode] = DeriveDefaultNodeVal();
}
TreeDPDict[ParentNode] =
DeriveNewNodeVal(TreeDPDict[ParentNode], DeriveSendVal(TreeDPDict[Node]));
}
// 木DPの結果
//foreach (var EachPair in TreeDPDict.OrderBy(pX => pX.Key)) {
// Console.WriteLine("TreeDPDict[{0}]=(ChildNodeCnt={1},DistanceSum={2})",
// EachPair.Key,
// EachPair.Value.ChildNodeCnt,
// EachPair.Value.DistanceSum);
//}
// ReRootingなDFSを行う
var sb = new System.Text.StringBuilder();
foreach (NodeInfo EachNodeInfo in ExecDFS2(1, TreeDPDict)) {
sb.AppendLine(EachNodeInfo.DistanceSum.ToString());
}
Console.Write(sb.ToString());
}
// 根から葉に向かってDFSしてノードのListを返す
struct JyoutaiDef1
{
internal int CurrNode;
internal int ParentNode;
}
static List<JyoutaiDef1> ExecDFS1(int pRootNode)
{
var WillReturn = new List<JyoutaiDef1>();
var Stk = new Stack<JyoutaiDef1>();
JyoutaiDef1 WillPush;
WillPush.CurrNode = pRootNode;
WillPush.ParentNode = -1;
Stk.Push(WillPush);
var VisitedSet = new HashSet<int>();
VisitedSet.Add(pRootNode);
while (Stk.Count > 0) {
JyoutaiDef1 Popped = Stk.Pop();
WillReturn.Add(Popped);
if (mToNodeListDict.ContainsKey(Popped.CurrNode) == false) {
continue;
}
foreach (int EachToNode in mToNodeListDict[Popped.CurrNode]) {
if (VisitedSet.Add(EachToNode)) {
WillPush.CurrNode = EachToNode;
WillPush.ParentNode = Popped.CurrNode;
Stk.Push(WillPush);
}
}
}
return WillReturn;
}
// ReRootingなDFSを行う
struct JyoutaiDef2
{
internal long PrevRootNode;
internal NodeInfo PrevRootVal;
internal long CurrRootNode;
internal NodeInfo CurrRootVal;
}
static IEnumerable<NodeInfo> ExecDFS2(long pRootNode, Dictionary<long, NodeInfo> pTreeDPDict)
{
var WillReturn = new List<long>();
var Stk = new Stack<JyoutaiDef2>();
JyoutaiDef2 WillPush;
WillPush.PrevRootNode = -1;
WillPush.PrevRootVal = new NodeInfo();
WillPush.CurrRootNode = pRootNode;
WillPush.CurrRootVal = pTreeDPDict[pRootNode];
Stk.Push(WillPush);
var VisitedSet = new HashSet<long>();
VisitedSet.Add(pRootNode);
var AnswerDict = new Dictionary<long, NodeInfo>();
while (Stk.Count > 0) {
JyoutaiDef2 Popped = Stk.Pop();
AnswerDict[Popped.CurrRootNode] = Popped.CurrRootVal;
// 累積値を管理する
int ChildCnt = 0;
if (mToNodeListDict.ContainsKey(Popped.CurrRootNode)) {
mToNodeListDict[Popped.CurrRootNode].Remove(Popped.PrevRootNode);
ChildCnt = mToNodeListDict[Popped.CurrRootNode].Count;
}
if (ChildCnt == 0) continue;
NodeInfo[] RunValSei = new NodeInfo[ChildCnt]; // 正方向の累積値
NodeInfo[] RunValRev = new NodeInfo[ChildCnt]; // 逆方向の累積値
long StaNode = mToNodeListDict[Popped.CurrRootNode][0];
long EndNode = mToNodeListDict[Popped.CurrRootNode][ChildCnt - 1];
RunValSei[0] = DeriveSendVal(pTreeDPDict[StaNode]);
RunValRev[RunValRev.GetUpperBound(0)] = DeriveSendVal(pTreeDPDict[EndNode]);
for (int I = 1; I <= ChildCnt - 1; I++) {
long CurrChildNode = mToNodeListDict[Popped.CurrRootNode][I];
RunValSei[I] =
DeriveNewNodeVal(RunValSei[I - 1], DeriveSendVal(pTreeDPDict[CurrChildNode]));
}
for (int I = ChildCnt - 2; 0 <= I; I--) {
long CurrChildNode = mToNodeListDict[Popped.CurrRootNode][I];
RunValRev[I] = DeriveNewNodeVal(RunValRev[I + 1], DeriveSendVal(pTreeDPDict[CurrChildNode]));
}
// 状態の遷移
for (int I = 0; I <= mToNodeListDict[Popped.CurrRootNode].Count - 1; I++) {
long CurrRootNode = mToNodeListDict[Popped.CurrRootNode][I];
if (VisitedSet.Add(CurrRootNode) == false) {
continue;
}
// 左方向の累積値
NodeInfo LeftRunVal = DeriveDefaultNodeVal();
bool HasLeftRunVal = false;
if (I > 0) {
LeftRunVal = RunValSei[I - 1];
HasLeftRunVal = true;
}
// 右方向の累積値
NodeInfo RightRunVal = DeriveDefaultNodeVal();
bool HasRightRunVal = false;
if (I < mToNodeListDict[Popped.CurrRootNode].Count - 1) {
RightRunVal = RunValRev[I + 1];
HasRightRunVal = true;
}
WillPush.PrevRootNode = Popped.CurrRootNode;
var PrevRootValKouhoList = new List<NodeInfo>();
if (HasLeftRunVal) PrevRootValKouhoList.Add(LeftRunVal);
if (HasRightRunVal) PrevRootValKouhoList.Add(RightRunVal);
if (Popped.PrevRootNode > -1) {
PrevRootValKouhoList.Add(DeriveSendVal(Popped.PrevRootVal));
}
WillPush.PrevRootVal = DeriveMergedSendVal(PrevRootValKouhoList);
WillPush.CurrRootNode = CurrRootNode;
var CurrRootValKouhoList = new List<NodeInfo>();
CurrRootValKouhoList.Add(pTreeDPDict[CurrRootNode]);
CurrRootValKouhoList.Add(DeriveSendVal(WillPush.PrevRootVal));
WillPush.CurrRootVal = DeriveMergedSendVal(CurrRootValKouhoList);
Stk.Push(WillPush);
}
}
foreach (var EachPair in AnswerDict.OrderBy(pX => pX.Key)) {
yield return EachPair.Value;
}
}
}