MCF
Contest: Educational Codeforces Round 139 (Rated for Div. 2)
Difficulty rating: 2800
Tags: flows

You are given a graph consisting of $$$n$$$ vertices and $$$m$$$ directed arcs. The $$$i$$$-th arc goes from the vertex $$$x_i$$$ to the vertex $$$y_i$$$, has capacity $$$c_i$$$ and weight $$$w_i$$$. No arc goes into the vertex $$$1$$$, and no arc goes from the vertex $$$n$$$. There are no cycles of negative weight in the graph (it is impossible to travel from any vertex to itself in such a way that the total weight of all arcs you go through is negative).

You have to assign each arc a flow (an integer between $$$0$$$ and its capacity, inclusive). For every vertex except $$$1$$$ and $$$n$$$, the total flow on the arcs going to this vertex must be equal to the total flow on the arcs going from that vertex. Let the flow on the $$$i$$$-th arc be $$$f_i$$$, then the cost of the flow is equal to $$$\sum \limits_{i = 1}^{m} f_i w_i$$$. You have to find a flow which minimizes the cost.

Sounds classical, right? Well, we have some additional constraints on the flow on every edge:

- if $$$c_i$$$ is even, $$$f_i$$$ must be even;
- if $$$c_i$$$ is odd, $$$f_i$$$ must be odd.

Can you solve this problem?

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 100$$$; $$$1 \le m \le 200$$$).

Then $$$m$$$ lines follow. The $$$i$$$-th of them contains four integers $$$x_i$$$, $$$y_i$$$, $$$c_i$$$, and $$$w_i$$$ ($$$1 \le x_i \le n - 1$$$; $$$2 \le y_i \le n$$$; $$$x_i \ne y_i$$$; $$$1 \le c_i \le 100$$$; $$$-100 \le w_i \le 100$$$). These integers describe the $$$i$$$-th arc.

Additional constraints on the input:

- there are no negative cycles in the graph.

Output format:
If a flow satisfying all of the constraints does not exist, print Impossible.

Otherwise, print two lines:

- the first line should contain one word Possible;
- the second line should contain $$$m$$$ integers $$$f_1, f_2, \dots, f_m$$$.

If there are multiple answers, print any of them. Note that the cost of the flow should be minimized.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Example input:
3 3
1 2 3 -10
1 2 3 -15
2 3 2 0

Example output:
Possible
1 1 2

Example input:
3 3
1 2 3 -10
1 2 3 -15
2 3 3 0

Example output:
Impossible

Editorial:
This problem is solved using minimum cost flows (duh).
Suppose all arcs have even capacity. Then we can just divide each arc's capacity by $$$2$$$ and solve a usual minimum cost flow problem. However, when we have arcs with odd capacity, it's not that simple. We will deal with them as follows: split an arc with capacity $$$2k+1$$$ into two arcs: one with capacity $$$2k$$$, the other with capacity $$$1$$$, and somehow enforce that the second arc must be saturated. We cannot divide all arcs by $$$2$$$ now, because that would lead to non-integer capacities; instead, we will exclude these arcs with capacity $$$1$$$ and somehow handle the fact that they must be saturated, and only then divide all capacities by $$$2$$$.
Okay, how do we handle the edges we deleted? For each vertex, let's check if the number of such arcs connected to it is even. If it is not — the total flow for this vertex cannot be $$$0$$$, so it's impossible to find the answer (the only case when it might be possible is if this vertex is the source or the sink; in this case, we need to check that both of these vertices have an odd number of arcs we want to delete connected to them, and consider an additional arc $$$1 \rightarrow n$$$ with capacity $$$1$$$ and weight $$$0$$$ to make it even).
If for each vertex, the number of odd arcs connected to it is even, let's consider how much excess flow these arcs bring into the vertices. For example, if a vertex has $$$4$$$ ingoing odd arcs, it has $$$4$$$ units of flow going into it, which will be lost if we remove the edges we want to ignore. To handle this, add a new source and a new sink to our network (let's call them $$$s$$$ and $$$t$$$), and process excess flow going into the vertex using an arc from $$$s$$$ to that vertex (in the previous example, we can add an arc from $$$s$$$ to the vertex with capacity $$$2$$$ — not $$$4$$$ since we divide all capacities by $$$2$$$). Similarly, excess flow going outside the vertex can be processed with an arc from that vertex to $$$t$$$. We need to make sure that all these edges must be saturated.
Okay, what about actually running the flow from $$$1$$$ to $$$n$$$? We can do it as in "flow with lower bounds" problem by adding an arc $$$n \rightarrow 1$$$ with infinite capacity... Wait a minute, this may cause a negative cycle to appear! If your implementation of mincost flow handles them, you can use this approach; but if you don't want to mess with negative cycles, instead do the following:
• add an arc $$$s \rightarrow 1$$$ and an arc $$$n \rightarrow t$$$, both with infinite capacities, to make sure that flow can go from $$$1$$$ to $$$n$$$;
• since these arcs don't have to be saturated, but other arcs going from $$$s$$$ or into $$$t$$$ must be saturated, set the costs of these "other" arcs to $$$-10^9$$$.
Okay, that's it — we just need to find the minimum cost flow in the resulting network. The constraints are low enough so any minimum cost flow algorith can pass.