Description

In hell, there are $n$ sinners waiting for judgment, numbered from $1$ to $n$. There are $m$ connections of sin among the sinners, numbered from $1$ to $m$. Each connection has a value of $1$ or $2$ and connects exactly two sinners.

Define a sinner's arrogance as the sum of the values of the connections between them and all other sinners. There may be more than one connection between two sinners; in that case, the values of all those connections should be counted. Because these sinners have borne too much evil, they have become disharmonious. Specifically, each sinner's arrogance is an odd number.

Now, God is going to judge them. The judgment works as follows: orient every connection, so that among the two sinners connected by this connection, one receives punishment and the other receives redemption, and their values are both equal to the value of this connection.

Because God upholds the Father's mercy and hopes the sinners receive punishment and redemption more evenly, He requires that after the judgment, for each sinner, the absolute value of the difference between the total punishment value and the total redemption value they receive must be exactly $1$.

Since God is busy, He asks you, in the name of the Father, to find a way to perform the judgment. Because the Father's instruction cannot be wrong, such a method must exist.

Problem summary

Given an undirected graph with $n$ vertices and $m$ edges, where each edge weight is either $1$ or $2$. It is guaranteed that for every vertex, the sum of weights of incident edges is odd. You need to orient all edges so that for every vertex, the absolute value of the difference between the sum of incoming edge weights and the sum of outgoing edge weights is exactly $1$. A solution is guaranteed to exist. Output any valid solution.

Input Format

The first line contains two positive integers $n,m$, meaning there are $n$ sinners and $m$ connections of sin.

The next $m$ lines describe the edges. The $(i+1)$-th line contains three positive integers $u_i,v_i,w_i$, meaning the $i$-th connection connects $u_i$ and $v_i$ and has value $w_i$.

Output Format

Output one line with $m$ digits. The $i$-th digit is $0$ if $u_i$ receives punishment and $v_i$ receives redemption; it is $1$ if $v_i$ receives punishment and $u_i$ receives redemption.

4 5
1 2 1
1 3 2
2 3 1
2 4 1
4 1 2

00100

Hint

Sample explanation

The oriented graph is as follows:

More samples can be found in the attachment trial_sample.zip.

Constraints

This problem uses bundled testdata.

• Special property A: all edge weights are $1$, and between any two vertices there is only one simple path, and there are no multiple edges.
• Special property B: for the same vertex, it is connected to at most one edge with weight $1$ and at most one edge with weight $2$.

For $100\%$ of the testdata: $1 \le u_i,v_i \le n \le 10^6$, $1 \le m \le 3 \times 10^6$, and $w_i \in \{1,2\}$.

In the attachment trial_sample.zip:

• trial_sample1.in is sample #1.
• trial_sample2.in satisfies special property A.
• trial_sample3.in satisfies special property B.
• trial_sample4.in does not satisfy any special property.

There is also checker.exe in the same directory.

Notes

The input and output are large, so please use fast I/O methods.

This problem provides the Special Judge source code and checker.exe for debugging. On Windows, usage is as follows:
In the command line, run the command in the target folder:

checker.exe data.in data.out data.out

Here, data.in is the input data file, and data.out is the output file produced by your program. Check the judging result.

• Perfect answer. means the answer is correct.
• Wrong answer on node x, and the difference is d. means the answer is wrong: for node $x$, the absolute value of the difference between the sum of incoming edge weights and the sum of outgoing edge weights is $d$ instead of $1$.
• Invalid answer. means the output string length is incorrect or it contains invalid characters.

Be sure to keep the output format correct, otherwise the Special Judge may return unpredictable results such as Unknown Error.

Translated by ChatGPT 5