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.
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).
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.
4 31 2 B2 3 B1 4 G
G B B G
3 31 2 G2 3 G1 3 B
-1
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.
All $$$3$$$ sculptures are consistent with this assignment.
For the second test case, it can be shown that no valid assignment exists.
| Name |
|---|


