给定一个由 $$$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$$$ 必须是奇数。
你能解决这个问题吗?
输入
第一行包含两个整数 $$$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$$$ 条弧。
输入的附加限制:
- 图中没有负循环。
输出
如果不存在满足所有约束的流,则打印 Impossible。
否则,打印两行:
- 第一行应包含一个单词“可能”;
- 第二行应包含 $$$m$$$ 整数 $$$f_1, f_2, \dots, f_m$$$。
如果有多个答案,请打印其中任何一个。请注意,流量成本应最小化。
示例
输入 #1
3 3 1 2 3 -10 1 2 3 -15 2 3 2 0
输出 #1
Possible 1 1 2
输入 #2
3 3 1 2 3 -10 1 2 3 -15 2 3 3 0
输出 #2
Impossible
输入 #3
3 3 1 2 3 -10 1 2 3 -15 2 3 4 0
输出 #3
Possible 1 3 4
输入#4
6 7 5 6 9 -40 1 2 3 -10 1 4 5 20 4 5 7 30 2 5 1 -15 1 3 3 5 3 5 3 0
输出#4
Possible 5 1 1 1 1 3 3