Apricot Rules 公司刚刚在其网络上安装了一个关键的安全更新。该网络包含一台源计算机，所有其他计算机都通过一系列一条或多条直接双向连接与源计算机相连。

这种更新会自动传播：一旦某台计算机首次收到更新，它会立即开始将更新传输给所有直接与它相连的计算机。每条直接连接都有一个延迟值：传输更新所需的秒数（双向传输所需时间相同）。因此，更新不会瞬间传播到所有计算机。

Apricot Rules 的工程师不知道这些延迟值，但他们知道它们都是正整数。他们希望你根据最近一次实验中观察到的更新传播情况，帮助推断出这些延迟值可能是多少。

Apricot Rules 的工程师仅在源计算机上安装了更新，然后等待它在整个系统中传播，直到每台计算机都收到更新。他们记录了一些关于更新如何传播的信息。具体来说，对于除源计算机之外的每一台计算机 $K$，你确切地知道以下两种信息之一：

• 源计算机收到更新的时间与 $K$ 首次收到更新的时间之间相差的精确秒数。
• 在 $K$ 之前严格先收到更新的其他计算机（包括源计算机）的数量。

注意，多台计算机可能在同一时间收到更新。

你需要计算出每两条计算机之间直接连接的延迟（以秒为单位）。每个延迟值必须是不超过 $10^6$ 的正整数。你提供的延迟集合必须与所有已知信息一致。题目保证至少存在一种一致的延迟分配方式。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $C$ 和 $D$：分别表示计算机的数量和直接连接的数量。计算机编号从 $1$ 到 $C$，其中 $1$ 号计算机为源计算机。

下一行包含 $C-1$ 个整数 $X_2, X_3, \dots, X_C$。若 $X_i$ 为正数，表示计算机 $i$ 在计算机 $1$ 收到更新 $X_i$ 秒后收到更新。若 $X_i$ 为负数，表示在计算机 $i$ 之前严格先收到更新的其他计算机数量为 $-X_i$（此数量包含源计算机）。

此后有 $D$ 行，表示网络中的 $D$ 条直接连接。第 $i$ 行包含两个整数 $U_i$ 和 $V_i$，表示计算机 $U_i$ 和 $V_i$ 之间存在直接连接。

输出格式

对于每个测试用例，输出一行 Case #x: y1 y2 ... yD，其中 $x$ 是测试用例编号（从 $1$ 开始），$y_i$ 是分配给第 $i$ 条直接连接的延迟（以秒为单位，且不超过 $10^6$ 的正整数）。

数据范围

$1 \le T \le 100$ $2 \le C \le 100$ $C - 1 \le D \le 1000$ $1 \le U_i < V_i \le C$，对于所有 $i$ $(U_i, V_i) \neq (U_j, V_j)$，对于所有 $i \neq j$ 除源计算机外，所有计算机都通过一系列一条或多条直接连接与源计算机相连。 保证至少存在一种与输入一致的延迟分配方式。

测试集 1（可见判定）

$-C < X_i < 0$，对于所有 $i$。（你将获得所有计算机的第二种类型信息。）

测试集 2（隐藏判定）

$-C < X_i \le 1000$，对于所有 $i$。 $X_i \neq 0$，对于所有 $i$。

样例

样例输入 1

3
4 4
-1 -3 -2
1 2
1 3
2 4
3 4
4 4
-1 -1 -1
1 4
1 2
1 3
2 3
3 2
-2 -1
2 3
1 3

样例输出 1

Case #1: 5 10 1 5
Case #2: 2020 2020 2020 2020
Case #3: 1000000 1000000

说明

在样例 1 中，下图展示了样例输出所对应的计算机网络。第 $i$ 台计算机由标有 $i$ 的圆圈表示。连接两个圆圈的线表示直接连接。线上的数字表示该直接连接的延迟。

在样例 2 中，前三条连接需要具有相同的延迟，而第四条连接可以是任何有效的延迟。注意，$-2, 0, 1000001$ 和 $3.14$ 都是无效延迟的例子。

在样例 3 中，请记住连接是双向的，因此更新可以从计算机 $3$ 传播到计算机 $2$。任何两个有效的延迟值在这里都适用。

以下情况不会出现在测试集 1 中，但可能出现在测试集 2 中：

1
6 9
10 -2 -5 15 20
1 2
1 3
2 3
2 4
2 5
3 5
3 6
4 5
5 6

其中一个正确的输出是 10 12 4 15 8 3 9 7 5，如下图所示：