Parity Constraint Maximum Flow

A flow network $(G, c, s, t)$ is defined as follows.

• $G$ is a directed graph $(V, E)$.
• $c : E \rightarrow \mathbb{R}^+$ is a function giving the capacity of each edge.
• $s, t \in V$ are the source and the sink, respectively, and $s \ne t$.

An $s$-$t$ flow $f$ on a flow network $(G, c, s, t)$ satisfies the following.

• For every $e \in E$, $0 \le f(e) \le c(e)$.
• For every $v \in V-\{s, t\}$, $\sum_{(u,v) \in E} f(u,v) = \sum_{(v,w) \in E} f(v,w)$.

The value of the flow $f$ is $|f| = \sum_{(s,v) \in E} f(s,v) - \sum_{(v,s) \in E} f(v,s) = \sum_{(v,t) \in E} f(v,t) - \sum_{(t,v) \in E} f(t,v)$.

A maximum flow is an $s$-$t$ flow with the largest value. If every $c(e)$ is an integer, a maximum flow in which every $f(e)$ is an integer can be found in polynomial time. Two such algorithms are the Edmonds-Karp Algorithm, which runs in $O(VE^2)$, and Dinic's Algorithm, which runs in $O(V^2 E)$.

A function $p : E \rightarrow \{0, 1\}$ is also given. An $s$-$t$ flow $f$ that satisfies the following conditions is called a parity constraint flow.

• For every $e \in E$, $f(e)$ is an integer.
• $f(e) \equiv p(e) \mod 2$.

The parity constraint flow with the largest value is called a parity constraint maximum flow.

Given a flow network $(G, c, s, t)$ and a function $p$, find a parity constraint maximum flow.

$N$ and $M$ are the number of vertices and edges of the graph $G=(V, E)$.

$u_i$ and $v_i$ mean that there is an edge from $u_i$ to $v_i$, and $c_i$ and $p_i$ are $c(u_i, v_i)$ and $p(u_i, v_i)$, respectively.

The input is given in the following format.

N M s t
u_1 v_1 c_1 p_1
⋯
u_M v_M c_M p_M

On the first line, print the value of the parity constraint maximum flow $f$. If no parity constraint flow exists, print -1.

If a parity constraint flow exists, print $f(u_i, v_i)$ on line $i+1$ for each $i = 1, \cdots, M$.

If there are multiple answers, print any of them.

• $2 \le N \le 300$
• $1 \le M \le 23\,000$
• $1 \le s, t \le N$, $s \ne t$
• $1 \le u_i, v_i \le N$, $u_i \ne v_i$
• $u_i \ne t$, $v_i \ne s$
• $1 \le c_i \le 1\,000\,000\,000$
• $p_i \in \{0, 1\}$
• No graph has two or more edges between the same pair of vertices.
• All numbers in the input are integers.