题目描述

Dave 是一位已经退休的计算机科学老教授，但他仍然维护着一个本地社区计算机网络。

每位社区成员都有一台计算机，每台计算机配有三张网卡，其中一些网卡之间通过电缆相连。整个网络保持连通，并且按照长期以来节约资源的传统，所使用的电缆数量保持为使网络连通所需的最小值。

因此，任意时刻网络都是一棵树。

社区成员之间的通信习惯非常稳定。对于某些计算机对，已知它们之间每秒需要传输的数据包数量。

对于编号为 $i,j$ 的两台计算机：

• $d_{ij}$ 表示它们之间最短路径经过的电缆数量；
• $c_{ij}$ 表示它们之间每秒传输的数据包数量。

网络的通信压力定义为

未在输入中给出的计算机对可以视为 $c_{ij}=0$。

由于网络建成已久，当前连接方式不一定仍然最优。Dave 决定在更换旧电缆的同时逐步优化网络。

对于输入中依次给出的每一条旧电缆，他执行以下操作：

1. 拆除这条旧电缆；
2. 使用一条新电缆重新连接网络，使得到的网络通信压力尽可能小；
3. 若有多种连接方式达到相同的最小通信压力，则选择端点编号字典序最小的一对。

更具体地说，设候选连接的两个端点都按从小到大书写。若 $(u_1,u_2)$ 与 $(v_1,v_2)$ 产生相同的通信压力，并且

• $u_1<v_1$，或
• $u_1=v_1$ 且 $u_2<v_2$，

则必须选择 $(u_1,u_2)$。

上图展示了样例中第一次重连操作：先拆除一条旧电缆，再加入一条新电缆。

由于每台计算机只有三张网卡，Dave 不能任意连接两台计算机。如果某台计算机当前已经连接了三台其他计算机，就不能再为它增加一条电缆。

可以证明，每一步总能找到一种合法连接；例如，重新连接刚刚被拆开的那两个端点一定是可行的。

请为每一次旧电缆更换操作求出 Dave 应加入的新电缆。

输入格式

第一行包含一个整数 $n$，表示计算机数量。

接下来 $n-1$ 行，第 $i$ 行包含两个整数 $a_i,b_i$，表示旧电缆 $i$ 连接的两台计算机。旧电缆将严格按照输入顺序被拆除和替换。

初始网络保证连通，且每台计算机的度数不超过 $3$。

随后一行包含一个整数 $d$，表示存在非零通信需求的计算机对数量。

接下来 $d$ 行，每行包含三个整数 $s_i,t_i,w_i$，表示计算机 $s_i$ 与 $t_i$ 之间每秒传输 $w_i$ 个数据包。

输出格式

输出 $n-1$ 行。

第 $i$ 行包含两个整数 $x_i,y_i$，其中 $x_i<y_i$，表示在第 $i$ 次操作中加入的新电缆连接计算机 $x_i$ 和 $y_i$。

由于题目规定了最小通信压力和字典序最小的决策规则，正确输出唯一。

数据范围

• $2\le n\le 2\cdot 10^3$；
• $1\le a_i<b_i\le n$；
• 初始网络是一棵树；
• 初始时每个顶点的度数不超过 $3$；
• $2\le d\le 10^4$；
• $1\le s_i<t_i\le n$；
• $1\le w_i\le 10^9$。

样例

输入

4
1 2
2 3
3 4
6
1 2 1
1 3 10
1 4 1
2 3 10
2 4 1
3 4 10

输出

1 3
2 3
3 4