問題文

$X$ と $Y$ の関係式 $P$（$X=Y$ または $X \neq Y$）を証明するとは，以下の行為のことを指します．

• $2$ つの変数 $v_1, v_2$ の関係式（$v_1 = v_2$ または $v_1 \neq v_2$）を，$1$ 個以上並べる．このとき，並べられた式が全て成り立つならば，$P$ も成り立つ，という命題は真である必要がある．

今，$N$ 個の変数 $x_1, x_2, \dots, x_N$ が与えられます．これらの変数は，任意の整数値をとることができます．また，これらの変数について，$M$ 個の関係式がわかっています．

$i(1 \leq i \leq M)$ 番目の式は，$A_i, B_i, C_i$ を用いて表されるものであり，その内容は $C_i = 1$ ならば $x_{A_i} = x_{B_i}$，$C_i = 2$ ならば $x_{A_i} \neq x_{B_i}$，というものです．

さて，$M$ 個の関係式から $1$ 個以上の式を並べて，$x_1$ と $x_N$ の間の関係式を証明したいです．

これらの関係式から，$x_1 = x_N$ であることが証明できるか，または $x_1 \neq x_N$ であることが証明できるかを判定し，どちらかが証明できる場合は並べる必要のある式の個数の最小値を求めてください．

なお，矛盾する入力は与えられないことが制約より保証されます．

$T$ 個のテストケースが与えられるので，それぞれについて答えてください．

制約

• 入力は全て整数
• $1 \leq T \leq 10^4$
• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $1 \leq A_i < B_i \leq N$
• $1 \leq C_i \leq 2$
• $(A_i, B_i) \neq (A_j, B_j) (i \neq j)$
• $1$ つの入力ファイルに対する $N$ の総和は $2 \times 10^5$ 以下
• $1$ つの入力ファイルに対する $M$ の総和は $2 \times 10^5$ 以下
• 矛盾した入力は与えられない

入力

入力は以下の形式で標準入力から与えられる．ここで，$\mathrm{case}_i$ は $i(1 \leq i \leq T)$ 番目のテストケースを表す．

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

各ケースは以下の形式で与えられる．

$N$ $M$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$\cdots$
$A_M$ $B_M$ $C_M$

出力

$T$ 個のテストケースに対して，それぞれ以下のように出力せよ．各テストケースの出力の末尾には改行を加えること．

• $x_1 = x_N$ が証明できるならば，$1$ 行目に Same を出力し，$2$ 行目に必要な式の数の最小値を出力せよ．
• $x_1 \neq x_N$ が証明できるならば，$1$ 行目に Different を出力し，$2$ 行目に必要な式の数の最小値を出力せよ．
• $x_1 = x_N$ と $x_1 \neq x_N$ のどちらも証明できないならば，Unknown とのみ出力せよ．

サンプル

3
4 3
1 2 1
2 3 2
2 4 1
2 1
1 2 2
5 4
1 2 1
2 3 1
1 3 1
4 5 2

Same
2
Different
1
Unknown