패리티 제약 최대 유량

flow network $(G, c, s, t)$는 다음과 같이 정의된다.

• $G$는 방향 그래프 $(V, E)$이다.
• $c : E \rightarrow \mathbb{R}^+$는 각 간선의 용량을 나타내는 함수이다.
• $s, t \in V$는 각각 source와 sink이며, $s \ne t$이다.

주어진 flow network $(G, c, s, t)$에 대한 $s$-$t$ flow $f$는 다음 조건을 만족한다.

• 모든 $e \in E$에 대해 $0 \le f(e) \le c(e)$이다.
• 모든 $v \in V-\{s, t\}$에 대해 $\sum_{(u,v) \in E} f(u,v) = \sum_{(v,w) \in E} f(v,w)$이다.

flow $f$의 값은 $|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)$로 정의된다.

maximum flow는 값이 최대인 $s$-$t$ flow이다. 모든 $c(e)$가 정수이면, 모든 $f(e)$가 정수인 maximum flow를 다항 시간에 구할 수 있음이 알려져 있다. 이러한 다항 시간 알고리즘의 예로 시간 복잡도 $O(VE^2)$의 Edmonds-Karp Algorithm과 시간 복잡도 $O(V^2 E)$의 Dinic's Algorithm이 있다.

여기에 함수 $p : E \rightarrow \{0, 1\}$이 추가로 주어진다. 다음 조건을 만족하는 $s$-$t$ flow $f$를 parity constraint flow라고 한다.

• 모든 $e \in E$에 대해 $f(e)$는 정수이다.
• $f(e) \equiv p(e) \mod 2$이다.

parity constraint flow 중 값이 최대인 것을 parity constraint maximum flow라고 한다.

flow network $(G, c, s, t)$와 함수 $p$가 주어졌을 때, parity constraint maximum flow를 구해 보자.

$N$과 $M$은 그래프 $G=(V, E)$의 정점 개수와 간선 개수이다.

$u_i$와 $v_i$는 $u_i$에서 $v_i$로 향하는 간선이 있음을 뜻하고, $c_i$와 $p_i$는 각각 $c(u_i, v_i)$와 $p(u_i, v_i)$이다.

입력은 다음과 같이 주어진다.

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

첫 번째 줄에 parity constraint maximum flow $f$의 값을 출력한다. parity constraint flow가 존재하지 않으면 -1을 출력한다.

parity constraint flow가 존재하면 $i = 1, \cdots, M$에 대해 $(i+1)$번째 줄에 $f(u_i, v_i)$의 값을 출력한다.

답이 여러 개이면 그중 아무것이나 출력하면 된다.

• $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\}$
• 두 정점 사이에 간선이 두 개 이상 있는 그래프는 주어지지 않는다.
• 입력에 주어진 수는 모두 정수이다.