{"problem":{"name":"F. Flow Control","description":{"content":"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 adjustin","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF990F"},"statements":[{"statement_type":"Markdown","content":"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$.\n\nThe 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$.\n\nIn 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).\n\nCan you choose the integers $f_1$, $f_2$, ..., $f_m$ in such a way that all requirements on incoming and outcoming flows are satisfied?\n\n## Input\n\nThe first line contains an integer $n$ ($1 \\le n \\le 2 \\cdot 10^5$) — the number of junctions.\n\nThe second line contains $n$ integers $s_1, s_2, \\dots, s_n$ ($-10^4 \\le s_i \\le 10^4$) — constraints for the junctions.\n\nThe third line contains an integer $m$ ($0 \\le m \\le 2 \\cdot 10^5$) — the number of pipes.\n\n$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.\n\n## Output\n\nIf 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.\n\nOtherwise output _\"Impossible\"_ in the only line.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"你需要处理一个非常复杂的供水系统。该系统由 $n$ 个节点和 $m$ 条管道组成，第 $i$ 条管道连接节点 $x_i$ 和 $y_i$。\n\n你唯一能做的操作是调整管道。你需要选择 $m$ 个整数 $f_1$, $f_2$, ..., $f_m$ 作为管道的设定值。第 $i$ 条管道将每秒从节点 $x_i$ 向节点 $y_i$ 输送 $f_i$ 单位的水（如果 $f_i$ 为负，则管道每秒从节点 $y_i$ 向节点 $x_i$ 输送 $| f_i |$ 单位的水）。允许将 $f_i$ 设置为任意介于 $-2 \\dot{\\cdot} 10^9$ 到 $2 \\dot{\\cdot} 10^9$ 之间的整数。\n\n为了使系统正常工作，存在一些约束条件：对于每个 $i \\in [1, n]$，第 $i$ 个节点关联一个数 $s_i$，表示该节点的流入流量与流出流量之差必须**恰好**为 $s_i$（如果 $s_i$ 非负，则第 $i$ 个节点每秒必须接收 $s_i$ 单位的水；如果为负，则该节点每秒必须向其他节点输送 $| s_i |$ 单位的水）。\n\n你能否选择整数 $f_1$, $f_2$, ..., $f_m$，使得所有关于流入和流出流量的要求均被满足？\n\n第一行包含一个整数 $n$（$1 \\leq n \\leq 2 \\dot{\\cdot} 10^5$）——节点的数量。\n\n第二行包含 $n$ 个整数 $s_1, s_2, \\dots, s_n$（$-10^4 \\leq s_i \\leq 10^4$）——各节点的约束条件。\n\n第三行包含一个整数 $m$（$0 \\leq m \\leq 2 \\dot{\\cdot} 10^5$）——管道的数量。\n\n接下来的 $m$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$1 \\leq x_i, y_i \\leq n$，$x_i \\ne y_i$）——描述第 $i$ 条管道。保证每个无序对 $(x, y)$ 在输入中最多出现一次（即在 $(x, y)$ 首次出现后，不会再出现 $(x, y)$ 或 $(y, x)$）。保证任意两个节点之间都存在一条沿管道连接的路径。\n\n如果你能选择整数 $f_1, f_2, \\dots, f_m$，使得所有关于流入和流出流量的要求均被满足，则在第一行输出 _\"Possible\"_。然后输出 $m$ 行，第 $i$ 行应包含 $f_i$ —— 所选的管道设定值。管道按输入中出现的顺序编号。\n\n否则，仅在一行中输出 _\"Impossible\"_。\n\n## Input\n\n第一行包含一个整数 $n$（$1 \\leq n \\leq 2 \\dot{\\cdot} 10^5$）——节点的数量。第二行包含 $n$ 个整数 $s_1, s_2, \\dots, s_n$（$-10^4 \\leq s_i \\leq 10^4$）——各节点的约束条件。第三行包含一个整数 $m$（$0 \\leq m \\leq 2 \\dot{\\cdot} 10^5$）——管道的数量。第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$1 \\leq x_i, y_i \\leq n$，$x_i \\ne y_i$）——描述第 $i$ 条管道。保证每个无序对 $(x, y)$ 在输入中最多出现一次（即在 $(x, y)$ 首次出现后，不会再出现 $(x, y)$ 或 $(y, x)$）。保证任意两个节点之间都存在一条沿管道连接的路径。\n\n## Output\n\n如果你能选择整数 $f_1, f_2, \\dots, f_m$，使得所有关于流入和流出流量的要求均被满足，则在第一行输出 _\"Possible\"_。然后输出 $m$ 行，第 $i$ 行应包含 $f_i$ —— 所选的管道设定值。管道按输入中出现的顺序编号。否则，仅在一行中输出 _\"Impossible\"_。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions:**\n\n- Let $ G = (V, E) $ be an undirected graph with $ |V| = n $ junctions and $ |E| = m $ pipes.\n- Each edge $ e_i = (x_i, y_i) \\in E $ corresponds to a directed flow variable $ f_i \\in \\mathbb{Z} $, where:\n  - $ f_i > 0 $: flow from $ x_i $ to $ y_i $,\n  - $ f_i < 0 $: flow from $ y_i $ to $ x_i $,\n  - $ f_i = 0 $: no flow.\n- Each vertex $ v_j \\in V $ has a net flow requirement $ s_j \\in \\mathbb{Z} $:  \n  $$\n  \\sum_{\\substack{e_i = (x_i, y_i) \\\\ x_i = j}} f_i - \\sum_{\\substack{e_i = (x_i, y_i) \\\\ y_i = j}} f_i = s_j\n  $$\n\n**Constraints:**\n\n1. For all $ j \\in [1, n] $:  \n   $$\n   \\sum_{i: x_i = j} f_i - \\sum_{i: y_i = j} f_i = s_j\n   $$\n\n2. $ f_i \\in \\mathbb{Z} $, and $ |f_i| \\leq 2 \\cdot 10^9 $ (feasibility of range is assumed given large bounds).\n\n3. The graph $ G $ is connected.\n\n**Objective:**\n\nDetermine whether there exists an assignment $ \\vec{f} = (f_1, \\dots, f_m) \\in \\mathbb{Z}^m $ satisfying the above system of linear equations.\n\n**Note:** The system is a flow conservation system on an undirected graph with specified net flows at nodes. The sum of all $ s_j $ must be zero for feasibility (since total inflow = total outflow).\n\n**Necessary condition:**\n$$\n\\sum_{j=1}^n s_j = 0\n$$\n\nIf this fails, output \"Impossible\".\n\nIf satisfied, the system is a standard **flow feasibility problem on an undirected graph with node demands**. Since the graph is connected and undirected, and edge capacities are unbounded (only integer constraint), the problem reduces to solving a system of $ n $ linear equations in $ m $ variables over $ \\mathbb{Z} $, with rank $ n-1 $ (due to dependency: sum of equations = 0).\n\nThis system is always feasible if $ \\sum s_j = 0 $, because:\n\n- The incidence matrix of a connected undirected graph has rank $ n - 1 $,\n- The demand vector $ \\vec{s} $ lies in the column space of the incidence matrix (since $ \\sum s_j = 0 $),\n- Hence, there exists a real-valued flow $ \\vec{f} \\in \\mathbb{R}^m $ satisfying the constraints,\n- Since the incidence matrix is totally unimodular, and $ \\vec{s} \\in \\mathbb{Z}^n $, there exists an **integer** solution $ \\vec{f} \\in \\mathbb{Z}^m $.\n\n**Therefore:**\n\n- If $ \\sum_{j=1}^n s_j \\neq 0 $: **Impossible**\n- Else: **Possible**, and an integer solution exists.\n\nTo construct a solution: pick a spanning tree of the graph, assign flows bottom-up from leaves to root (arbitrarily root the tree), and set flows on tree edges to satisfy node demands. Non-tree edges can be set to 0 (since the system is underdetermined and we only need one solution).\n\n---\n\n**Formal Output:**\n\n- If $ \\sum_{j=1}^n s_j \\ne 0 $:  \n  `Impossible`\n\n- Else:  \n  `Possible`  \n  Then output $ m $ integers $ f_1, f_2, \\dots, f_m $ — any integer solution to the flow conservation equations.\n\n*(Construction algorithm is implied by standard flow on tree + cycle adjustment, but output only requires existence and one valid assignment.)*","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF990F","tags":["dfs and similar","dp","greedy","trees"],"sample_group":[["4\n3 -10 6 1\n5\n1 2\n3 2\n2 4\n3 4\n3 1","Possible\n4\n-6\n8\n-7\n7"],["4\n3 -10 6 4\n5\n1 2\n3 2\n2 4\n3 4\n3 1","Impossible"]],"created_at":"2026-03-03 11:00:39"}}