F. Flow Controltime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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?InputThe 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.OutputIf 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.ExamplesInput43 -10 6 151 23 22 43 43 1OutputPossible4-68-77Input43 -10 6 451 23 22 43 43 1OutputImpossible
Input43 -10 6 151 23 22 43 43 1
OutputPossible4-68-77
['dfs and similar', 'dp', 'greedy', 'trees', '*2400']