CF990F Flow Control

你需要管理一个非常复杂的供水系统。该系统由 $n$ 个节点和 $m$ 条管道组成，第 $i$ 条管道连接节点 $x_i$ 和 $y_i$。 你唯一能做的事情就是调整管道。你需要选择 $m$ 个整数 $f_1, f_2, \dots, f_m$，并将它们作为管道的设置。第 $i$ 条管道每秒会从节点 $x_i$ 向节点 $y_i$ 输送 $f_i$ 单位的水（如果 $f_i$ 为负数，则表示该管道每秒从 $y_i$ 向 $x_i$ 输送 $|f_i|$ 单位的水）。允许将 $f_i$ 设置为任意整数，范围为 $-2 \cdot 10^9$ 到 $2 \cdot 10^9$。 为了使系统正常工作，需要满足以下约束：对于每个 $i \in [1, n]$，第 $i$ 个节点有一个数 $s_i$，表示该节点的流入与流出水量的差必须恰好为 $s_i$（如果 $s_i$ 非负，则第 $i$ 个节点每秒必须净流入 $s_i$ 单位的水；如果 $s_i$ 为负，则第 $i$ 个节点每秒必须向其他节点净流出 $|s_i|$ 单位的水）。 你能否选择整数 $f_1, f_2, \dots, f_m$，使得所有节点的流入与流出水量的要求都被满足？

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示节点数。 第二行包含 $n$ 个整数 $s_1, s_2, \dots, s_n$（$-10^4 \le s_i \le 10^4$），表示每个节点的流量约束。 第三行包含一个整数 $m$（$0 \le m \le 2 \cdot 10^5$），表示管道数。 接下来的 $m$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n$，$x_i \ne y_i$），表示第 $i$ 条管道连接的两个节点。保证每对无序节点对 $(x, y)$ 在输入中最多出现一次（即不会有重复的 $(x, y)$ 或 $(y, x)$）。保证对于任意两节点之间都存在一条由管道连接的路径。

如果你能选择整数 $f_1, f_2, \dots, f_m$，使得所有节点的流入与流出水量的要求都被满足，则第一行输出 "Possible"。接下来输出 $m$ 行，第 $i$ 行输出 $f_i$，表示第 $i$ 条管道的设置。管道按输入顺序编号。 否则，输出一行 "Impossible"。

由 ChatGPT 4.1 翻译