题目描述
小杨拿到一棵 个点的树,以 为根。接下来有 次询问,每次给出一个结点 ,他想知道 的子树里深度最大的结点是哪个;如果有多个结点深度相同,输出编号最小的那个。请你对每次询问给出答案。
输入格式
第一行一个整数 ;接下来 行每行两个整数 , ;然后一行一个整数 ;接下来 行每行一个整数 。
输出格式
共 行,每行一个整数。
样例
输入
5 1 2 1 3 3 4 3 5 3 1 3 2
输出
4 4 2
数据范围
- 对于 30% 的数据, (每次扫子树可过)。
- 对于 60% 的数据, 。
- 对于 100% 的数据,,满档含星形(大量同深并列),。