Flow Control
Contest: Educational Codeforces Round 45 (Rated for Div. 2)
Difficulty rating: 2400
Tags: dfs and similar, dp, greedy, trees

You have to handle a very complex water distribution system. The system consists of $$$n$$$ junctions and $$$m$$$ pipes, $$$i$$$-th pipe connects junctions $$$x_i$$$ and $$$y_i$$$.

The only thing you can do is adjusting the pipes. You have to choose $$$m$$$ integer numbers $$$f_1$$$, $$$f_2$$$, ..., $$$f_m$$$ and use them as pipe settings. $$$i$$$-th pipe will distribute $$$f_i$$$ units of water per second from junction $$$x_i$$$ to junction $$$y_i$$$ (if $$$f_i$$$ is negative, then the pipe will distribute $$$|f_i|$$$ units of water per second from junction $$$y_i$$$ to junction $$$x_i$$$). It is allowed to set $$$f_i$$$ to any integer from $$$-2 \cdot 10^9$$$ to $$$2 \cdot 10^9$$$.

In order for the system to work properly, there are some constraints: for every $$$i \in [1, n]$$$, $$$i$$$-th junction has a number $$$s_i$$$ associated with it meaning that the difference between incoming and outcoming flow for $$$i$$$-th junction must be exactly $$$s_i$$$ (if $$$s_i$$$ is not negative, then $$$i$$$-th junction must receive $$$s_i$$$ units of water per second; if it is negative, then $$$i$$$-th junction must transfer $$$|s_i|$$$ units of water per second to other junctions).

Can you choose the integers $$$f_1$$$, $$$f_2$$$, ..., $$$f_m$$$ in such a way that all requirements on incoming and outcoming flows are satisfied?

Input format:
The first line contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of junctions.

The second line contains $$$n$$$ integers $$$s_1, s_2, \dots, s_n$$$ ($$$-10^4 \le s_i \le 10^4$$$) — constraints for the junctions.

The third line contains an integer $$$m$$$ ($$$0 \le m \le 2 \cdot 10^5$$$) — the number of pipes.

$$$i$$$-th of the next $$$m$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \ne y_i$$$) — the description of $$$i$$$-th pipe. It is guaranteed that each unordered pair $$$(x, y)$$$ will appear no more than once in the input (it means that there won't be any pairs $$$(x, y)$$$ or $$$(y, x)$$$ after the first occurrence of $$$(x, y)$$$). It is guaranteed that for each pair of junctions there exists a path along the pipes connecting them.

Output format:
If you can choose such integer numbers $$$f_1, f_2, \dots, f_m$$$ in such a way that all requirements on incoming and outcoming flows are satisfied, then output "Possible" in the first line. Then output $$$m$$$ lines, $$$i$$$-th line should contain $$$f_i$$$ — the chosen setting numbers for the pipes. Pipes are numbered in order they appear in the input.

Otherwise output "Impossible" in the only line.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
4
3 -10 6 1
5
1 2
3 2
2 4
3 4
3 1

Example output:
Possible
4
-6
8
-7
7

Example input:
4
3 -10 6 4
5
1 2
3 2
2 4
3 4
3 1

Example output:
Impossible

Editorial:
The answer is "Impossible" if and only if the sum of values is not equal to $$$0$$$. Writing some number on edge does not change the total sum and the goal of the problem is to make $$$0$$$ in each vertex, thus getting $$$0$$$ in total.
The algorithm is simple: you get an arbitrary spanning tree (with dfs or dsu), output the difference between sums of values of subtrees (can be calculated with dfs) for edges in this tree and $$$0$$$ for the rest of edges.
Let's take an arbitrary correct answer. If is has some cycle in graph of edges with non-zero numbers on them, then you can remove it. For example, select any edge on it and subtract the number on it from all the edges of the cycle. This doesn't break the correctness of the answer, as you change both in and out flows for each vertex by the same value. Now that edge has $$$0$$$. This way, any answer can be transformed to tree. And for any edge on tree we want to tranfer excess water units from the larger subtree to the smaller.
Overall complexity: $$$O(n + m)$$$.