题目描述
在某个游戏中有一个魔法师角色,他的技能树上有n个不同的技能,被编号为0到n-1,除了初始技能外每个技能都需要学习了一个前置技能才可以学习,该技能也被称作其前置技能的子技能。技能树的根节点也就是初始技能是该角色被创建时就已经掌握了,而向一个分支学习直到没有子技能的时候,这个没有子技能的技能就被叫做终极技能。现在我们知道了所有技能之间的关系,请你求出初始技能的编号、子技能最多的技能编号、终极技能的数量和掌握各个技能分别最少需要学习多少个技能。
输入描述
第一行一个整数n,表示技能的总数。
接下来n-1行每行两个整数x和y,表示技能x是技能y的前置技能,输入保证不存在环。
其中n≤100,000
输出描述
第一行三个整数表示初始技能编号、子技能最多的技能编号和终极技能的数量,若子技能最多的技能有多个解则输出编号最小的一个。
第二行n个整数分别表示掌握每个技能分别最少需要学习多少个技能。
样例输入
8
0 1
1 3
2 6
2 4
3 7
2 5
0 2
样例输出
0 2 4
0 1 1 2 2 2 2 3
提示
读入数据存好树之后,依次求解即可。对于第二行,可以在bfs过程中求出树上每个节点的深度