A15658 | MCF

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?

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.

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.