Problem Statement

You are given a graph $G$ with $N$ vertices and $0$ edges. The vertices are numbered from $1$ to $N$.
$Q$ queries of the following forms are given, so process them in order on the graph $G$.

• 1 u v : Connect vertex $u$ and vertex $v$ with an edge.
• 2 v : Output one vertex that is not connected to vertex $v$. If no such vertex exists, output -1.

Input

$N\ \ Q$
${\rm Query}_{1}$
${\rm Query}_{2}$
${\rm Query}_{3}$
$\ \ \ \ \vdots$
${\rm Query}_{i}$
$\ \ \ \ \vdots$
${\rm Query}_{Q}$

• $1\leq N \leq 2\times 10^{5}$
• $1\leq Q \leq 2\times 10^{5}$
• For ${\rm Query}_{i}$:
  
  For a type 1 query

  $1\ u_{i}\ v_{i}$

  For a type 2 query

  $2\ \ v_{i}$

  ・$1 \leq u_{i}, v_{i} \leq N$


• All inputs are integers.

Output

If $K$ type 2 queries are given, output the answer to the $i$-th type 2 query on line $i\ (1 \leq i \leq K) $. If there are multiple solutions, any of them will be accepted. Print a newline at the end.

Sample

4 7
2 1
1 1 2
2 1
1 3 4
2 4
1 1 3
2 1

2
3
1
-1