Electrons Flow Experiment

Mr. Šikić, a chemistry teacher, is conducting an experiment with \( n \) metal balls and \( m \) copper wires. He connects some of the metal balls with copper wires so that they are all connected (directly or indirectly). At the beginning, none of the balls carries any charge and the electrons in the wires are at rest.

He demonstrates the concept of electric charge by charging the metal balls one after another. When a ball is charged, it can either be charged positively or negatively. When a ball is charged positive, all electrons in the wires connected to it are attracted toward it; when charged negative, the electrons are repelled away from it. Regardless of the previous state of a wire, charging a ball always produces the same effect on every wire connected to it.

Consider a wire connecting ball \( u \) and ball \( v \). Suppose the ball that is charged later in the sequence determines the final electron flow. In particular:

• If the later-charged ball is positive, electrons flow from the earlier-charged ball to the later-charged ball.
• If the later-charged ball is negative, electrons flow from the later-charged ball to the earlier-charged ball.

Therefore, for a wire with desired electron flow from ball \( u \) to ball \( v \), there are two possibilities:

• If ball \( u \) is charged before ball \( v \), then ball \( v \) must be charged positive.
• If ball \( v \) is charged before ball \( u \), then ball \( u \) must be charged negative.

Similarly, if the desired electron flow is from ball \( v \) to ball \( u \), then either ball \( v \) comes before \( u \) with \( u \) charged negative, or ball \( u \) comes before \( v \) with \( v \) charged positive.

Your task is to determine a sequence in which to charge the metal balls and assign a charge (either '+' or '-') to each ball so that, after all balls are charged, the electron flow in every wire is as specified.

Note: It is guaranteed that a valid solution exists. In our solution below we choose the simple strategy of assigning all balls a positive charge and then finding a charging order that meets the following rule: For each wire given by three integers \( u \), \( v \), and \( d \), if \( d = 0 \) (i.e. desired flow from \( u \) to \( v \)), we require that ball \( u \) is charged before ball \( v \); if \( d = 1 \) (i.e. desired flow from \( v \) to \( u \)), then ball \( v \) must be charged before ball \( u \>.

inputFormat

The first line contains two integers \( n \) and \( m \) ( 1 ≤ n, m ≤ 10⁵ or as specified by the problem constraints).

Each of the next \( m \) lines contains three integers \( u \), \( v \), and \( d \) (1 ≤ u, v ≤ n and d is either 0 or 1). If \( d = 0 \), the desired electron flow on the wire connecting balls \( u \) and \( v \) is from \( u \) to \( v \). If \( d = 1 \), the desired flow is from \( v \) to \( u \).

outputFormat

Output two lines.

The first line should contain a permutation of the integers from 1 to \( n \) representing the order in which the metal balls are charged.

The second line should be a string of \( n \) characters. The \( i \)th character in this line is either '+' or '-' and represents the charge assigned to the metal ball that is charged in the \( i \)th step.

In the sample solutions provided below, we assign all balls a positive charge ('+') and compute a charging order via topological sorting of a directed graph defined as follows: For each input wire (u, v, d), if d = 0, add a directed edge from u to v, and if d = 1, add a directed edge from v to u.

sample

3 2
1 2 0
2 3 0

1 2 3
+++

</p>