Balanced Edge Orientation with Odd Weights

In Hell there are n sinners, numbered from \(1\) to \(n\), and there are m undirected connections among them. Each connection \(e\) connects two distinct sinners and has a weight \(w_e\) which is either \(1\) or \(2\). It is guaranteed that for every sinner \(v\) the sum of the weights of all connections incident to \(v\), denoted by \(F(v)\), is odd.

The conceit of sinner \(v\) is defined as the sum of the weights on all connections between \(v\) and all other sinners. In the upcoming divine judgment, every connection will be given a direction. When a connection \(e\) (of weight \(w_e\)) is directed from sinner \(u\) to sinner \(v\), then sinner \(u\) receives a punishment of \(w_e\) while sinner \(v\) receives a redemption of \(w_e\>.

For fairness the divine command requires that after all connections are oriented, every sinner \(v\) must satisfy \[ |{\rm Out}(v) - {\rm In}(v)| = 1, \] where \({\rm Out}(v)\) is the total weight of connections directed out of \(v\) (punishment) and \({\rm In}(v)\) is the total weight of connections directed into \(v\) (redemption). Equivalently, if we denote by \(d(v)= {\rm Out}(v)-{\rm In}(v)\), then \[ d(v)= \begin{cases} 1, \\ -1, \end{cases} \] and note that since \(F(v)={\rm Out}(v)+{\rm In}(v)\) is odd, the equation \[ 2\cdot{\rm Out}(v)-F(v)= d(v)\] forces \[ {\rm Out}(v)= \frac{F(v)+ d(v)}{2} \quad \text{and} \quad {\rm In}(v)= \frac{F(v)- d(v)}{2} . \]

It can be shown that one may choose the numbers \(d(v)\in\{1,-1\}\) (with the side condition that \(\sum_{v=1}^{n} d(v)=0\)) and orient all connections accordingly. In other words, there exists a subset \(X\subseteq\{1,2,\dots,n\}\) with \(|X|=\frac{n}{2}\) (assume \(n\) is even) such that for every sinner \(v\) if \(v\in X\) then we set \(d(v)=1\) and otherwise \(d(v)=-1\).

Your task is to output any valid orientation of all m connections so that for every sinner \(v\), the absolute difference between the total punishment and total redemption is exactly \(1\). In the input the connections are given in an arbitrary order; the output should contain for each connection either 0 or 1: if the output is 0 then the connection is oriented as given in the input (i.e. from the first endpoint to the second), and if 1 then the connection is reversed. It is guaranteed that under the given conditions a solution exists.

inputFormat

The first line contains two integers \(n\) and \(m\) (with \(n\) even), representing the number of sinners and the number of connections.

Each of the following \(m\) lines contains three integers \(u\), \(v\) and \(w\) (\(1 \le u, v \le n,\, u \neq v,\) and \(w\) is either 1 or 2), describing a connection between sinner \(u\) and sinner \(v\) with weight \(w\).

It is guaranteed that for every sinner \(v\), the sum of the weights of connections incident to \(v\) is odd.

outputFormat

Output a single line with \(m\) integers separated by spaces. The \(i\)th integer should be 0 if the \(i\)th connection (in input order) is oriented from its first endpoint to its second endpoint, or 1 if it is reversed.

In the resulting orientation, for every sinner \(v\), if we denote \({\rm Out}(v)\) as the sum of weights of connections directed out of \(v\) and \({\rm In}(v)\) as the sum of weights directed into \(v\), then \(|{\rm Out}(v)-{\rm In}(v)|=1\) must hold.

sample

2 1
1 2 1

0