给定一个无向图，每条边都被染成红色（R）或蓝色（B）。如果存在一条路径，使得路径上边的颜色按顺序与字符串 $s$ 的字符匹配，则称由字符 R 和 B 组成的字符串 $s$ 是“可走的”（walkable）。路径不需要是简单路径，因此允许重复访问边和顶点。

例如，考虑下图：

在这种情况下，字符串 BRRBB 是可走的，因为可以使用以下路径：

请找出长度最短的不可走字符串，或者确定所有字符串都是可走的。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^4$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 2 \cdot 10^5, 0 \le m \le 2 \cdot 10^5$)，分别表示图的顶点数和边数。

接下来的 $m$ 行，每行描述图中的一条边，包含两个整数 $u$ 和 $v$ 以及一个字符 $c$ ($1 \le u, v \le n, u \neq v, c = \text{B 或 R}$)，表示边的端点及其颜色。保证每对无序顶点之间最多只有一条边。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$，且所有测试用例中 $m$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行，包含一个长度最短的不可走字符串；如果所有字符串都是可走的，则输出 $-1$。

如果存在多个答案，输出任意一个即可。

样例

输入 1

5
4 4
1 2 B
3 1 B
3 4 R
4 1 R
3 3
1 2 R
2 3 R
3 1 R
4 2
1 2 R
3 4 B
7 10
1 2 B
1 4 R
2 4 B
4 5 B
6 7 R
6 2 R
5 7 B
3 6 B
3 7 R
1 7 B
3 0

输出 1

BRB
B
RB
-1
R

说明

第一个样例中的图对应于上图。可以证明，该图上所有长度不超过 2 的字符串都是可走的。

第二个样例中的图不包含蓝色边，因此字符串 B 是不可走的。

可以证明，第四个样例中的图上所有字符串都是可走的。