I 教授と T 教授は，グラフの問題が好きである．
今日は，以下の問題について考えてみることにした．

JOI 王国には，$1, 2, ... , N$ と番号付けられた $N$ 個の都市と，$M$ 本の道路がある．$i$ 本目の道路は番号 $A_i$ の都市と番号 $B_i$ の都市を双方向に繋いでおり，文字 $C_i$ が書かれている．

E869120 君は，都市 $1$ から都市 $N$ へ，道路のみを使って移動することにした．道路に書かれている文字を通った順番に全てメモしたとき，JOI 文字列になるように移動することはできるか．もしできる場合は， 作れる最短の JOI 文字列の長さはいくつか．

ただし，同じ都市を二度通ったり，同じ道路を二度通ったりする移動方法も許されるものとする．

ただし，JOI 文字列 とは，以下の条件をすべて満たす文字列のことを指す．JOI 文字列としては，例えば 'JOI', 'JJOOII', 'JJJOOOIII' などが挙げられる．

• 文字列の長さ |S| が 3 の倍数である．
• 最初の $|S|/3$ 文字が 'J'，次の $|S|/3$ 文字が 'O'，最後の $|S|/3$ 文字が 'I' である．

教授たちに代わって，上枠の問題を解け．

• $1 \leq T \leq 5$
• $2 \leq N \leq 20000$
• $1 \leq M \leq 20000$
• $1 \leq A_i < B_i \leq N$
• $(A_i, B_i) \neq (A_j, B_j)$
• $C_i$ は 'J', 'O', 'I' のいずれかである．
• どの都市からどの都市へも，いくつかの道路を通じて行き来することができる．
• $C_i$ 以外の入力はすべて整数である．

この課題は，7 個の小課題から成る．

各入力データ について,以下の形式で入力が与えられる．

$T$
($1$ 個目のテストケースの情報)
($2$ 個目のテストケースの情報)
...
($T$ 個目のテストケースの情報)

各テストケース について,以下の形式で入力が与えられる．

• 1 行目に，整数 $N, M$ が空白区切りで与えられる．
• $1 + i (1 \leq i \leq N)$ 行目に，整数 $A_i, B_i, C_i$ が空白区切りで与えられる．

$T$ 行に渡って出力せよ．
$i$ 行目には，$i$ 個目のテストケースにおける答えを，以下の通りに出力せよ．

メモした文字列を JOI 文字列にすることができない場合，$-1$ と出力せよ．
メモした文字列を JOI 文字列にすることができる場合，文字列の最短の長さを出力せよ．