APIOBike 是 APIO 市新推出的一项共享单车服务。全市设立了多个站点，允许用户在任何站点借车或还车。由于其便捷和低廉的成本，它已迅速成为 APIO 市最重要的交通方式。然而，APIOBike 遇到了所有共享单车服务都会面临的一个常见问题：不同站点之间借车和还车率的不平衡。这导致一些站点几乎没有单车，使得附近的居民无法借车，而另一些站点则堆积了当地居民不需要的单车。

为了解决这个问题，APIOBike 计划每晚调度一辆再平衡卡车，在各站点间重新分配单车，确保每个站点都能维持适当的单车数量。APIO 市共有 $N$ 个站点，编号为 $0, 1, \dots, N - 1$。通过观察，APIOBike 发现每天晚上，站点 $i$ 的单车数量始终为固定值 $A[i]$，且夜间没有人借车或还车。公司目标是让每天早上每个站点 $i$ 恰好有 $B[i]$ 辆单车。

在这些 $N$ 个站点中，有 $N - 1$ 条专门供再平衡卡车使用的道路。每条道路连接两个不同的站点，卡车只能在这些道路上行驶。每条道路的长度为一个单位。这个站点网络是连通的，确保卡车可以在任意两个站点之间行驶。每天晚上，APIOBike 必须调度一辆再平衡卡车，以确保每个站点 $i$ 恰好有 $B[i]$ 辆单车。卡车可以从任意站点出发，也可以在任意站点结束其路线。

再平衡开始时，卡车是空的。当卡车位于某个站点时，司机可以从站点向卡车装载任意数量的单车，或者从卡车向站点卸载任意数量的单车。卡车和站点对单车的容量没有限制，但任何位置的单车数量绝不能低于零。公司希望确定完成再平衡的最小可能行驶距离及其相应的策略。

实现细节

你需要实现以下过程：

std::pair<std::vector<int>, std::vector<long long>>
find_rebalancing_strategy(int N, 
                          std::vector<int> A, 
                          std::vector<int> B, 
                          std::vector<int> U,
                          std::vector<int> V)

• $A$：一个长度为 $N$ 的数组，其中 $A[i]$ 是每天晚上站点 $i$ 的单车数量。
• $B$：一个长度为 $N$ 的数组，其中 $B[i]$ 是每天早上站点 $i$ 的目标单车数量。
• $U, V$：长度为 $N - 1$ 的数组，表示道路网络。对于每个 $0 \le i < N - 1$，第 $i$ 条道路连接站点 $U[i]$ 和站点 $V[i]$。
• 对于每个测试用例，此过程最多被调用 $150\,000$ 次。

该过程应返回一对长度为 $k + 1$ 的数组 $(X, Y)$，表示一种再平衡策略：

• $X$：按时间顺序访问的站点索引序列。
• $Y$：在每个访问站点处的净单车交付量。对于每个 $0 \le j \le k$：
  • 如果 $Y[j] \ge 0$，司机从卡车向站点 $X[j]$ 卸载 $Y[j]$ 辆单车，使该站点的单车数量增加 $Y[j]$。
  • 如果 $Y[j] < 0$，司机从站点 $X[j]$ 向卡车装载 $-Y[j]$ 辆单车，使该站点的单车数量减少 $-Y[j]$。

一个行驶距离为 $k$ 的有效再平衡策略 $(X, Y)$ 必须满足以下条件：

• 对于每个 $0 \le j \le k$，$0 \le X[j] < N$。
• 对于每个 $0 \le j < k$，站点 $X[j]$ 和 $X[j + 1]$ 由一条道路直接相连。
• 对于每个 $0 \le j \le k$，$Y[j]$ 可以是任意整数。
• 对于每个站点 $0 \le i < N$ 和每个步骤 $0 \le j \le k$，令 $S_{i,j}$ 为所有满足 $0 \le t \le j$ 且 $X[t] = i$ 的步骤 $t$ 中 $Y[t]$ 的总和。
  • 站点 $i$ 的单车数量从不低于零：$A[i] + S_{i,j} \ge 0$。
  • 策略结束后，每个站点 $i$ 必须恰好包含 $B[i]$ 辆单车：$A[i] + S_{i,k} = B[i]$。

数据范围

• $2 \le N \le 300\,000$
• 每个测试用例中，所有调用 find_rebalancing_strategy 的 $N$ 之和不超过 $300\,000$。
• 对于每个 $0 \le i < N$，满足 $0 \le U[i], V[i] < N$ 且 $U[i] \neq V[i]$。
• 对于每个 $0 \le i < N$，满足 $0 \le A[i], B[i] \le 10^9$。
• 任意两个站点之间均可通行。
• $\sum_{i=0}^{N-1} A[i] = \sum_{i=0}^{N-1} B[i]$。
• 至少存在一个 $i$ 使得 $0 \le i < N$ 且 $A[i] \neq B[i]$。

子任务

这里，$T$ 是调用 find_rebalancing_strategy 的次数，$\sum N$ 是所有调用中 $N$ 的总和。

属性 P：对于每个 $0 \le i < N - 1$，$U[i] = i$ 且 $V[i] = i + 1$。对于每个 $0 \le i < N$，$A[i] \neq B[i]$。

如果返回的数组 $X$ 和 $Y$ 的长度恰好为 $k + 1$（其中 $k$ 是最小可能的行驶距离），但 $(X, Y)$ 不是一个有效策略，你将获得 50% 的分数。

样例

样例 1

考虑以下调用：

find_rebalancing_strategy(4,
 [10, 1, 5, 0],
 [10, 0, 3, 3],
 [0, 1, 1],
 [1, 2, 3])

APIO 市有 $N = 4$ 个站点。最初，各站点的单车数量为 $A = [10, 1, 5, 0]$，目标是每个站点有 $B = [10, 0, 3, 3]$ 辆单车。

假设再平衡卡车从站点 2 出发，并遵循以下步骤： 在站点 2，装载 2 辆单车到卡车上。站点 2 现在有 3 辆单车，卡车有 2 辆。 移动到站点 1，装载 1 辆单车到卡车上。站点 1 现在有 0 辆单车，卡车有 3 辆。 * 移动到站点 3，卸载 3 辆单车。站点 3 现在有 3 辆单车，卡车有 0 辆。

总移动距离为 2。该策略对应的返回数组为 $X = [2, 1, 3]$ 和 $Y = [-2, -1, 3]$。可以证明该策略达到了最小距离。因此，该过程应返回 ([2, 1, 3], [-2, -1, 3])。

样例 2

考虑以下调用：

find_rebalancing_strategy(5,
 [3, 0, 1, 2, 2],
 [2, 2, 1, 3, 0],
 [2, 2, 2, 2],
 [0, 4, 3, 1])

APIO 市有 $N = 5$ 个站点。最初，各站点的单车数量为 $A = [3, 0, 1, 2, 2]$，目标是每个站点有 $B = [2, 2, 1, 3, 0]$ 辆单车。

假设再平衡卡车从站点 0 出发，并遵循以下步骤： 在站点 0，装载 1 辆单车。 移动到站点 2，装载 1 辆单车。 移动到站点 1，卸载 2 辆单车。 移动到站点 2。 移动到站点 4，装载 2 辆单车。 移动到站点 2，卸载 1 辆单车。 * 移动到站点 3，卸载 1 辆单车。

总移动距离为 6。该策略对应的返回数组为 $X = [0, 2, 1, 2, 4, 2, 3]$ 和 $Y = [-1, -1, 2, 0, -2, 1, 1]$。可以证明该策略达到了最小距离。因此，该过程应返回 ([0, 2, 1, 2, 4, 2, 3], [-1, -1, 2, 0, -2, 1, 1])。

样例 3

考虑以下调用：

find_rebalancing_strategy(4,
 [3, 0, 5, 0],
 [2, 2, 3, 1],
 [0, 1, 2],
 [1, 2, 3])

一个最优解是 $X = [2, 1, 0, 1, 2, 3]$ 和 $Y = [-1, 1, -1, 1, -1, 1]$。该过程应返回 ([2, 1, 0, 1, 2, 3], [-1, 1, -1, 1, -1, 1])。其他有效策略，例如 $X = [2, 1, 0, 1, 2, 3]$ 和 $Y = [-2, 2, -1, 0, 0, 1]$，也被视为正确。

样例评测程序

输入的第一行应包含一个整数 $T$，即场景的数量。随后是 $T$ 个场景的描述，每个场景的格式如下：

输入格式 1

N
A[0] A[1] ... A[N-1]
B[0] B[1] ... B[N-1]
U[0] V[0]
U[1] V[1]
...
U[N-2] V[N-2]

输出格式 1

k
X[0] X[1] ... X[k]
Y[0] Y[1] ... Y[k]