您必须处理非常复杂的配水系统。该系统由 $$$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