English · Original
Chinese · Translation
Formal · Original
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
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
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.
[samples]
你需要处理一个非常复杂的供水系统。该系统由 $n$ 个节点和 $m$ 条管道组成，第 $i$ 条管道连接节点 $x_i$ 和 $y_i$。
你唯一能做的操作是调整管道。你需要选择 $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$ 之间的整数。
为了使系统正常工作，存在一些约束条件：对于每个 $i \in [1, n]$，第 $i$ 个节点关联一个数 $s_i$，表示该节点的流入流量与流出流量之差必须**恰好**为 $s_i$（如果 $s_i$ 非负，则第 $i$ 个节点每秒必须接收 $s_i$ 单位的水；如果为负，则该节点每秒必须向其他节点输送 $| s_i |$ 单位的水）。
你能否选择整数 $f_1$, $f_2$, ..., $f_m$，使得所有关于流入和流出流量的要求均被满足？
第一行包含一个整数 $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$）——管道的数量。
接下来的 $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)$）。保证任意两个节点之间都存在一条沿管道连接的路径。
如果你能选择整数 $f_1, f_2, \dots, f_m$，使得所有关于流入和流出流量的要求均被满足，则在第一行输出 _"Possible"_。然后输出 $m$ 行，第 $i$ 行应包含 $f_i$ —— 所选的管道设定值。管道按输入中出现的顺序编号。
否则，仅在一行中输出 _"Impossible"_。
## Input
第一行包含一个整数 $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)$）。保证任意两个节点之间都存在一条沿管道连接的路径。
## Output
如果你能选择整数 $f_1, f_2, \dots, f_m$，使得所有关于流入和流出流量的要求均被满足，则在第一行输出 _"Possible"_。然后输出 $m$ 行，第 $i$ 行应包含 $f_i$ —— 所选的管道设定值。管道按输入中出现的顺序编号。否则，仅在一行中输出 _"Impossible"_。
[samples]
**Definitions:**
- Let $ G = (V, E) $ be an undirected graph with $ |V| = n $ junctions and $ |E| = m $ pipes.
- Each edge $ e_i = (x_i, y_i) \in E $ corresponds to a directed flow variable $ f_i \in \mathbb{Z} $, where:
- $ f_i > 0 $: flow from $ x_i $ to $ y_i $,
- $ f_i < 0 $: flow from $ y_i $ to $ x_i $,
- $ f_i = 0 $: no flow.
- Each vertex $ v_j \in V $ has a net flow requirement $ s_j \in \mathbb{Z} $:
$$
\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
$$
**Constraints:**
1. For all $ j \in [1, n] $:
$$
\sum_{i: x_i = j} f_i - \sum_{i: y_i = j} f_i = s_j
$$
2. $ f_i \in \mathbb{Z} $, and $ |f_i| \leq 2 \cdot 10^9 $ (feasibility of range is assumed given large bounds).
3. The graph $ G $ is connected.
**Objective:**
Determine whether there exists an assignment $ \vec{f} = (f_1, \dots, f_m) \in \mathbb{Z}^m $ satisfying the above system of linear equations.
**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).
**Necessary condition:**
$$
\sum_{j=1}^n s_j = 0
$$
If this fails, output "Impossible".
If 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).
This system is always feasible if $ \sum s_j = 0 $, because:
- The incidence matrix of a connected undirected graph has rank $ n - 1 $,
- The demand vector $ \vec{s} $ lies in the column space of the incidence matrix (since $ \sum s_j = 0 $),
- Hence, there exists a real-valued flow $ \vec{f} \in \mathbb{R}^m $ satisfying the constraints,
- 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 $.
**Therefore:**
- If $ \sum_{j=1}^n s_j \neq 0 $: **Impossible**
- Else: **Possible**, and an integer solution exists.
To 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).
---
**Formal Output:**
- If $ \sum_{j=1}^n s_j \ne 0 $:
`Impossible`
- Else:
`Possible`
Then output $ m $ integers $ f_1, f_2, \dots, f_m $ — any integer solution to the flow conservation equations.
*(Construction algorithm is implied by standard flow on tree + cycle adjustment, but output only requires existence and one valid assignment.)*
API Response (JSON)
{
"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 adjustin...",
"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$ 为负，则管道每秒从节点 ...",
"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...",
"is_translate": false,
"language": "Formal"
}
]
}