邻家男孩

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在住着\(N\)户人家组成的幻想乡,每家每户都能够通过\(N - 1\)条无向边走到所有其他人家。如果把第一家人的位置拿来做参考,那么这就形成了一棵根节点为\(1\)的有根树。
传说,人人都喜欢邻家男孩,因为他们不仅身体健壮,而且生物学得很好——特别是对两栖动物有着深入的研究。
对于第\(i\)家人,他们把满足以下条件的\(j\)家里的小孩称为邻家男孩:
1. \(i \neq j\);
2. \(dis(1, i) = dis(1, j)\);
3. 若\(dis(1, i) = dis(1, k)\),那么有\(dis(i, j) \leq dis(i, k)\)。
换句话说,就是深度相同,且距离最近的点。
现在,你需要帮助幻想乡的各位怀着赞美之心的居民找到最近的邻家男孩;由于可能有很多个点满足条件,你只需要告诉他们最近的邻家男孩离他们有多远就行了。

输入格式

第一行一个正整数\(N\)。
第二行开始\(N - 1\)行,每行两个正整数表示\(u_i,v_i\),表示这两个点间有一条边权为\(1\)的无向边。

输出格式

输出\(N - 1\)行,第\(i\)行表示对于\(i + 1\)节点的答案。如果邻家男孩不存在,请输出-1

样例输入

7
1 2
2 3
1 4
4 5
4 6
6 7

样例输出

2
4
2
2
2
-1

样例解释

\(2 \rightarrow \{4\}\)
\(3 \rightarrow \{5, 6\}\)
\(4 \rightarrow \{2\}\)
\(5 \rightarrow \{6\}\)
\(6 \rightarrow \{5\}\)
\(7 \rightarrow\) Ø

约定与限制

一共二十组数据,编号从\(1\)到\(20\)。
对于第\(i\)组数据,\(N \leq 2 ^ i\)。
输入输出数据可能很大,请考虑采用不那么低效的输入输出方式。

听说考完半期已经没有什么好怕的了_20170421

未参加
状态
已结束
规则
OI
题目
3
开始于
2017-04-21 18:45
结束于
2017-04-21 21:45
持续时间
3.0 小时
主持人
参赛人数
0