S - Association

問題文

ある日，GyaosくんはImosちゃんと $2$ 人で連想ゲームをすることになりました．
Imosちゃんは $1$ 以上 $N$ 以下の整数 $A$ を思い浮かべているとき，$1$ 回連想すると，$1$ 以上 $N$ 以下の整数 $f(A)$ を代わりに思い浮かべます．
Imosちゃん「やっぱり，$1$ といったら $2$ だよねー」
Gyaosくん「、、、ん？」
GyaosくんはImosちゃんの連想のルールが全く分かりません．この時，Imosちゃんは $Q$ 回の発言を行います．発言の内容は以下のうちの $2$ つです．
Case1. 「やっぱり，$A$ といったら $B$ だよねー」
Case2. 「私さっき $X$ を $Y$ 回連想したから，今思い浮かべている数字分かる？」
Case1 のとき，1 A B が与えられます．このとき，$f(A)=B$ であることを意味し，これは不変です．また，Gyaosくんはそれを理解します．
Case2 のとき，2 X Y が与えられます．このとき，現時点でGyaosくんが理解している情報のみを用いてImosちゃんの質問の答えを出力してください．もし答えが $1$ つに定まらないときは，-1 と出力してください．

制約

• $N, Q$は整数
• $1 \leq N \leq 5 \cdot 10^4$
• $1 \leq Q \leq 2 \cdot 10^5$
• Case1 のとき，$A$ は整数で，$1 \leq A \leq N$
• Case1 のとき，$B$ は整数で，$1 \leq B \leq N$
• Case2 のとき，$X$ は整数で，$1 \leq X \leq N$
• Case2 のとき，$Y$ は整数で，$1 \leq Y \leq 10^9$

小課題

1. (20点) $N \leq 100, Q \leq 100, Y \leq 100$
2. (40点) $N \leq Q$, 始めの $N$ 回の発言でGyaosくんはImosちゃんの連想のルールをすべて理解する
3. (40点) 追加の制約はない

入力

入力は以下の形式で標準入力から与えられる．

$N~Q$

$Query_1$

$Query_2$

$...$

$Query_Q$

ここで $Query_i$ は $i$ 番目の発言を表し，以下のいずれかの形式で与えられる．

$1~A~B$

$2~X~Y$

出力

問題文の指示に従ってすべての出力を改行区切りで出力せよ．

入力例1

3 7
1 1 2
2 2 1
1 2 3
2 1 2
1 3 1
2 2 3
2 3 9
Copy

出力例1

-1
3
2
3
Copy

• $1$ 番目の発言：「やっぱり，$1$ といったら $2$ だよねー」
• $2$ 番目の発言：「私さっき $2$ を $1$ 回連想したから，今思い浮かべている数字分かる？」
  このとき，Gyaosくんは $1$ を $1$ 回連想したとき $2$ であることしか理解していません．よって，思い浮かべている数字を一つに定めることができないので -1 と出力します．
• $3$ 番目の発言：「やっぱり，$2$ といったら $3$ だよねー」
• $4$ 番目の発言：「私さっき $1$ を $2$ 回連想したから，今思い浮かべている数字分かる？」
  このとき，Gyaosくんは $1$ を $1$ 回連想すると $2$ になり，$2$ を $1$ 回連想すると $3$ になることを理解しています．したがって，$1$ を $2$ 回連想すると $3$ となることがわかるので 3 と出力します．
• $5$ 番目の発言：「やっぱり，$3$ といったら $1$ だよねー」
• $6$ 番目の発言：「私さっき $2$ を $3$ 回連想したから，今思い浮かべている数字分かる？」
  $2$ を $3$ 回連想すると $2$ となるので，2 と出力します．
• $7$ 番目の発言：「私さっき $3$ を $9$ 回連想したから，今思い浮かべている数字分かる？」
  $3$ を $9$ 回連想すると $3$ となるので，3 と出力します．

この入力例は小課題1,3の制約を満たします．

入力例2

5 3
1 1 2
1 1 2
1 3 1
Copy

出力例2

Copy

同じ入力を受け取ることや，一度も出力しないこともあります．
この入力例は小課題1,3の制約を満たします．