题目描述

随着碳中和时代的到来，韩国也引入了氢能列车。政府将 UCPC 车辆基地指定为氢能列车的枢纽基地，并计划把所有与氢能铁路有关的工作交给这里负责。

善宇负责管理氢能列车的燃料充电系统。车辆基地中共有 $N$ 个交叉点，编号为 $1$ 到 $N$；另有 $N-1$ 条轨道以树的形式连接这些交叉点。

每条轨道的长度恰好等于一节车厢的长度。因此，一列列车可以停放在连接某两个交叉点的简单路径上，并让每一节车厢恰好占据一条轨道。

所有轨道均为单线轨道，所以每条轨道上最多只能停放一列列车。不过，车厢之间的连接通道由柔软的橡胶制成，因此多列列车可以在交叉点处重叠。

部分交叉点安装了充电器。要给一列列车充电，必须使列车带有驾驶室的一端停在安装了对应充电器的交叉点处，从而连接充电器与驾驶室。由于列车的制造商和规格各不相同，每列列车只能使用指定交叉点处的充电器。

共有 $T$ 列列车需要进入基地充电。第 $j$ 列列车长 $l_j$ 节，并且必须使用交叉点 $p_j$ 处的充电器。

第一个样例的一种列车停放方案

请判断能否在不让任意两列列车共用同一条轨道的前提下停放所有列车；若可以，还需要输出一种具体方案。

输入格式

第一行包含一个整数 $N$，表示交叉点的数量。

接下来 $N-1$ 行描述轨道。第 $i$ 行包含两个整数 $s_i,e_i$，表示第 $i$ 条轨道连接交叉点 $s_i$ 与 $e_i$。

保证这些轨道构成一棵树。

第 $N+1$ 行包含一个整数 $T$，表示需要充电的列车数量。

接下来 $T$ 行描述列车。第 $j$ 行包含两个整数 $p_j,l_j$，表示第 $j$ 列列车必须使用交叉点 $p_j$ 处的充电器，且列车长度为 $l_j$ 节。

输出格式

若不存在停放所有 $T$ 列列车的方法，输出一行：

NO

否则，第一行输出：

YES

随后输出 $T$ 行。第 $j$ 行输出两个整数 $p_j,q_j$，表示将第 $j$ 列列车停放在交叉点 $p_j$ 到交叉点 $q_j$ 的简单路径上。

输出必须满足：

• 输出的 $p_j$ 与输入中第 $j$ 列列车指定的充电器位置相同；
• $p_j$ 到 $q_j$ 的简单路径长度恰好为 $l_j$；
• 任意两列列车使用的轨道互不重叠。

若存在多种方案，输出任意一种即可。

数据范围

• $2\le N\le 500\,000$；
• $1\le s_i,e_i\le N$；
• $1\le T<N$；
• $1\le p_j\le N$；
• $1\le l_j<N$。

样例 1

输入

12
1 6
7 10
4 8
3 6
10 12
5 7
11 4
1 9
2 10
7 1
10 4
3
6 3
8 3
2 2

输出

YES
6 5
8 12
2 7

样例 2

输入

5
1 2
2 3
2 4
3 5
2
2 2
5 1

输出

NO