AT_waipc_qual_c.Odd Even Counters

有一棵无向树，包含 $N$ 个顶点，顶点编号为 $1$ 到 $N$。每条边编号为 $1$ 到 $N-1$，边 $i$ 连接顶点 $A_i$ 和顶点 $B_i$。

每条边 $i$ 上有两个计数器 $x_i, y_i$。初始时，$x_i = y_i = 0$。

你可以进行如下操作任意多次（可以为 $0$ 次）：

• 任意选择树上的一条行走路径。更具体地，选择一个顶点序列 $(v_0, v_1, \ldots, v_k)$（其中 $v_i$ 和 $v_{i+1}$ 由一条边直接相连，$k$ 可以任意），令 $v_i$ 与 $v_{i+1}$ 之间的边为 $e_i$。然后，对所有偶数位置的 $i = 0,2,4,\ldots$，将 $x_{e_i}$ 的值加 $1$；对所有奇数位置的 $i = 1,3,5,\ldots$，将 $y_{e_i}$ 的值加 $1$。若同一条边在路径中多次出现，则每次出现相应的计数器都会增加。

每条边都有一个目标计数器值 $(X_i, Y_i)$。你的目标是让所有边的计数器变为 $(x_i, y_i) = (X_i, Y_i)$。

请判断是否有可能达成目标；若可能，输出所需操作次数的最小值。

请对每个测试用例分别作答。

输入通过标准输入给出，格式如下：

$T$ $case_1$ $case_2$ $ \vdots $ $case_T$

每个测试用例包含：

$N$ $A_1$ $B_1$ $X_1$ $Y_1$
$A_2$ $B_2$ $X_2$ $Y_2$
$\vdots$
$A_{N-1}$ $B_{N-1}$ $X_{N-1}$ $Y_{N-1}$

对于每个测试用例，

若无法达成目标，输出 -1；否则，输出所需的最小操作次数。

样例解释 1

例如，对于第 $1$ 个测试用例，按如下两步操作可达成目标：

• 选择路径 $(1,2,3)$，将 $x_1, y_2$ 的值各加 $1$。
• 选择路径 $(2,1)$，将 $x_1$ 的值加 $1$。

对于第 $2$ 和第 $3$ 个测试用例，无论如何操作都无法达到目标。

数据范围

• $1 \leq T \leq 125000$
• $2 \leq N \leq 250000$
• $1 \leq A_i, B_i \leq N$
• $0 \leq X_i, Y_i \leq 10^9$
• 输入的图均为树
• $T$ 个测试用例中所有 $N$ 的总和不超过 $250000$
• 输入均为整数

由 ChatGPT 5 翻译