邻家男孩
题目描述
在住着\(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\)。
输入输出数据可能很大,请考虑采用不那么低效的输入输出方式。
信息
- 难度
- 9
- 分类
- (无)
- 标签
- (无)
- 递交数
- 8
- 已通过
- 2
- 通过率
- 25%
- 上传者
相关
在下列比赛中: