A11807 | Flow Control

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?

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.

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.