CF1766F.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?

你被给定一个包含 $n$ 个顶点和 $m$ 条有向边的图。第 $i$ 条边从顶点 $x_i$ 指向顶点 $y_i$，其容量为 $c_i$、权重为 $w_i$。没有任何边指向顶点 $1$，也没有任何边从顶点 $n$ 出发。图中不存在负权环（即：无法从任意顶点出发，经过若干条边后回到自身，且所经过所有边的总权重为负）。

你需要为每条边分配一个流量（一个介于 $0$ 与该边容量（含端点）之间的整数）。对于除顶点 $1$ 和顶点 $n$ 外的每个顶点，流入该顶点的所有边的流量之和必须等于流出该顶点的所有边的流量之和。设第 $i$ 条边上的流量为 $f_i$，则该流的费用定义为 $\sum \limits_{i = 1}^{m} f_i w_i$。你需要找出一个使总费用最小的可行流。

听起来很经典，对吧？不过，我们对每条边上的流量还有额外的约束：

• 若 $c_i$ 为偶数，则 $f_i$ 必须为偶数；
• 若 $c_i$ 为奇数，则 $f_i$ 必须为奇数。

你能解决这个问题吗？

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.

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 100$；$1 \le m \le 200$）。

接下来是 $m$ 行。其中第 $i$ 行包含四个整数 $x_i$、$y_i$、$c_i$ 和 $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$）。这些整数描述第 $i$ 条有向边。

输入的额外约束条件：

• 图中不存在负权环。

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.

如果不存在满足所有约束条件的流，则输出 Impossible。

否则，输出两行：

• 第一行输出一个单词 Possible；
• 第二行输出 $m$ 个整数 $f_1, f_2, \dots, f_m$。

若存在多个解，输出任意一个即可。注意：该流的费用应最小化。