Minimum Absolute Weight Sum in a Colored Graph

You are given an undirected graph with n nodes and m edges. Each edge has one of two colors: red or black.

You need to assign a real number weight to each node such that for every edge:

• If the edge is black, then the sum of the weights of its endpoints is \(1\): \(x_u + x_v = 1\).
• If the edge is red, then the sum of the weights of its endpoints is \(2\): \(x_u + x_v = 2\).

Among all assignments satisfying these constraints, choose one that minimizes the sum of absolute values of all node weights, i.e. minimize \(\sum_{i=1}^{n} |x_i|\).

Output one such assignment.

inputFormat

The first line contains two integers n and m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 10⁵), representing the number of nodes and edges respectively.

Each of the following m lines contains two integers u and v (1-indexed) and a character c describing an edge. The character c is either 'B' or 'R', where 'B' indicates a black edge (with the constraint \(x_u+x_v=1\)) and 'R' indicates a red edge (with the constraint \(x_u+x_v=2\)).

If a node has no incident edge, there is no constraint on its weight (and you should choose its weight to minimize the objective, which is 0).

outputFormat

Output n real numbers separated by spaces, where the i-th number is the weight assigned to node i. The assignment must satisfy all edge constraints and the sum of absolute weights must be minimized.

sample

2 1
1 2 B

0 1