题目描述

给定一棵以 $1$ 号结点为根的树，结点编号 $1\sim n$。从根开始做深度优先遍历，访问某个结点的子结点时按编号从小到大进行。

按这个规则得到的结点访问序列就是这棵树的 DFS 序。记 $dfn_v$ 为结点 $v$ 在 DFS 序中的位置，$siz_v$ 为以 $v$ 为根的子树大小。

现在给出 $m$ 次询问，每次给出一个结点 $u$，请你回答以 $u$ 为根的子树在 DFS 序中占据的区间，以及子树大小。

输入格式

第一行一个整数 $n$。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示树上的一条边。

接下来一行一个整数 $m$。

接下来 $m$ 行，每行一个整数 $u$，表示一次询问。

输出格式

第一行 $n$ 个整数，表示这棵树的 DFS 序，相邻两个整数之间用一个空格隔开。

接下来 $m$ 行，每行两个整数，依次为 $dfn_u$ 与 $siz_u$。

输入输出样例 #1

输入 #1

4
1 2
1 3
3 4
2
3
1

输出 #1

1 2 3 4
3 2
1 4

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n,m\le 2\times 10^5$。