Problem Statement

Proving a relation $P$ between $X$ and $Y$ ($X=Y$ or $X \neq Y$) refers to the following act.

• List $1$ or more relations, each between $2$ variables $v_1, v_2$ ($v_1 = v_2$ or $v_1 \neq v_2$). Here, the proposition "if all the listed relations hold, then $P$ also holds" must be true.

You are given $N$ variables $x_1, x_2, \dots, x_N$. These variables can take any integer value. In addition, $M$ relations among these variables are known.

The $i(1 \leq i \leq M)$-th relation is represented by $A_i, B_i, C_i$. It states $x_{A_i} = x_{B_i}$ if $C_i = 1$, and $x_{A_i} \neq x_{B_i}$ if $C_i = 2$.

Now, you want to prove a relation between $x_1$ and $x_N$ by listing $1$ or more relations out of the $M$ relations.

Determine whether these relations can prove $x_1 = x_N$ or can prove $x_1 \neq x_N$, and if either can be proved, find the minimum number of relations that need to be listed.

It is guaranteed by the constraints that no contradictory input is given.

You are given $T$ test cases; answer each of them.

Constraints

• All input values are integers
• $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)$
• The sum of $N$ in $1$ input file is at most $2 \times 10^5$
• The sum of $M$ in $1$ input file is at most $2 \times 10^5$
• No contradictory input is given

Input

The input is given from standard input in the following format. Here, $\mathrm{case}_i$ represents the $i(1 \leq i \leq T)$-th test case.

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

Each case is given in the following format.

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

Output

For each of the $T$ test cases, output as follows. Add a newline at the end of the output for each test case.

• If $x_1 = x_N$ can be proved, print Same on line $1$, and print the minimum number of relations needed on line $2$.
• If $x_1 \neq x_N$ can be proved, print Different on line $1$, and print the minimum number of relations needed on line $2$.
• If neither $x_1 = x_N$ nor $x_1 \neq x_N$ can be proved, print only Unknown.

Sample

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