← 返回题目列表

Codeforces · 990/F

F. 流量控制

中文机器翻译题面 查看原题

您必须处理非常复杂的配水系统。该系统由 $$$n$$$ 交叉点和 $$$m$$$ 管道组成,第 $$$i$$$ 管道连接交叉点 $$$x_i$$$ 和 $$$y_i$$$。

你唯一能做的就是调整管道。您必须选择 $$$m$$$ 整数 $$$f_1$$$、$$$f_2$$$、...、$$$f_m$$$ 并将它们用作管道设置。 $$$i$$$-th 管道将每秒从交汇点 $$$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$$$-th 路口都有一个与之关联的数字 $$$s_i$$$,这意味着 $$$i$$$-th 路口的传入和传出流量之间的差异必须恰好为 $$$s_i$$$(如果 $$$s_i$$$ 不为负,则$$$i$$$-th 路口必须每秒接收 $$$s_i$$$ 单位的水;如果为负,则 $$$i$$$-th 路口必须每秒向其他路口传输 $$$|s_i|$$$ 单位的水。

您能否选择整数 $$$f_1$$$、$$$f_2$$$、...、$$$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)$$$ 之后不会有任何对 $$$(x, y)$$$ 或 $$$(y, x)$$$ )。确保每对连接点都存在一条沿着连接它们的管道的路径。

输出

如果你可以选择这样的整数 $$$f_1, f_2, \dots, f_m$$$ 以满足所有传入和传出流量的要求,则在第一行输出“Possible”。然后输出 $$$m$$$ 行,第 $$$i$$$ 行应包含 $$$f_i$$$ — 为管道选择的设置编号。管道按照它们在输入中出现的顺序进行编号。

否则在唯一的行中输出“不可能”。

示例

输入 #1

4
3 -10 6 1
5
1 2
3 2
2 4
3 4
3 1

输出 #1

Possible
4
-6
8
-7
7

输入 #2

4
3 -10 6 4
5
1 2
3 2
2 4
3 4
3 1

输出 #2

Impossible