B. Collaborative Clay
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A group of $$$n$$$ people (numbered $$$1$$$ to $$$n$$$) work on clay sculptures. Each person is either good (G) or bad (B) at sculpting.

$$$m$$$ sculptures were made, and each one was a collaboration between two different people. A sculpture turns out good if and only if both sculptors are good. If at least one of them is bad, it turns out bad.

You are given the result of every sculpture. Determine whether there is an assignment of G/B to all $$$n$$$ people consistent with every result. If there is, output any such assignment. If the results are contradictory (the sculptures were tampered with), output -1.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2\cdot 10^5$$$, $$$0 \le m \le 2\cdot 10^5$$$) — the number of people and sculptures, respectively.

Each of the next $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$) and a character $$$c$$$ (G or B), meaning sculptors $$$u$$$ and $$$v$$$ made a sculpture with result $$$c$$$ (G for good and B for bad).

Output

If no valid assignment exists, output -1.

Otherwise, output $$$n$$$ lines. The $$$i$$$th line should contain G or B, the skill of person $$$i$$$. If several assignments are valid, output any of them.

Examples
Input
4 3
1 2 B
2 3 B
1 4 G
Output
G
B
B
G
Input
3 3
1 2 G
2 3 G
1 3 B
Output
-1
Note

For the first test case, the output is G B B G, so persons $$$1$$$ and $$$4$$$ are good, and persons $$$2$$$ and $$$3$$$ are bad.

  • Sculpture $$$1$$$ is made by persons $$$1$$$ and $$$2$$$. Person $$$2$$$ is bad, so the sculpture turns out bad, which matches the input B.
  • Sculpture $$$2$$$ is made by persons $$$2$$$ and $$$3$$$. Both are bad, so the sculpture turns out bad, which matches the input B.
  • Sculpture $$$3$$$ is made by persons $$$1$$$ and $$$4$$$. Both are good, so the sculpture turns out good, which matches the input G.

All $$$3$$$ sculptures are consistent with this assignment.

For the second test case, it can be shown that no valid assignment exists.