Problem Statement

The raccoons are about to return to their hometowns.

The country where the raccoons live consists of $N$ towns and $M$ roads connecting pairs of different towns, and the towns are numbered from $1$ to $N$. The $i$-th road can be used to travel in both directions between towns $A_i$ and $B_i$.

You are given information on $Q$ queries in chronological order. The $j$-th query is one of the following $2$ types.

• Query $1$: $1$ prey animal of value $W_j$ appears in town $U_j$. This prey can be caught by visiting town $U_j$. The values $W_j$ of the prey that appear are all different.
• Query $2$: $1$ raccoon in town $S_j$ returns home to town $T_j$. Since passing along the same road repeatedly would attract natural enemies, the same road cannot be used more than once.
  During this trip, the raccoon catches, as a souvenir, $1$ prey animal with the maximum value among those that can be caught along the way (including towns $S_j$ and $T_j$). The raccoon may pass through town $T_j$ along the way, as long as it finally reaches town $T_j$. If there is no prey that can be caught, the raccoon reluctantly returns home empty-handed.
  Caught prey disappears, so the same prey cannot be caught again.

We are curious about the value of the prey each raccoon caught as a souvenir. For each query $2$, determine the value of the prey caught.

Input

$N$ $M$ $Q$
$A_1$ $B_1$
$A_2$ $B_2$
:
$A_M$ $B_M$
$Query_1$
$Query_2$
:
$Query_Q$

Line $1$ contains the number of towns $N(2 \le N \le 100\ 000)$, the number of roads $M(1 \le M \le 200\ 000)$, and the number of queries $Q(1 \le Q \le 200\ 000)$.

From line $2$, the following $M$ lines give information on the roads. The $i$-th of these lines indicates that the $i$-th road can be used to travel in both directions between town $A_i$ and town $B_i(1 \le A_i \lt B_i \le N)$. The same pair $A_i, B_i$ is never given more than once.
It is also guaranteed that every town can be reached from every other town using the roads.

The following $Q$ lines then give information on the queries in chronological order. The $j$-th of these lines is the information on the $j$-th query, given in one of the following formats.

$1$ $U_j$ $W_j$

$2$ $S_j$ $T_j$

• If the first value is $1$, it is query $1$. This means that $1$ new prey animal of value $W_j(1 \le W_j \le 10^9)$ appears in town $U_j(1 \le U_j \le N)$, and it is guaranteed that the values $W_j$ are different across queries.
• If the first value is $2$, it is query $2$. This means that $1$ raccoon returns home from town $S_j$ to town $T_j(1 \le S_j, T_j \le N)$, and it is guaranteed that $S_j \ne T_j$.

Output

The number of output lines equals the number of queries $2$.

In the order in which the queries $2$ are given, output the value of the prey that the raccoon caught as a souvenir. If the raccoon returned home empty-handed, output $-1$.

Sample

Sample 1

Input

4 4 7
1 2
2 3
3 4
2 4
2 1 2
1 1 13
1 1 133
1 3 1333
2 1 2
2 4 3
2 4 1

Output

-1
1333
-1
133

The given graph is shown in the figure below.

• In the $1$st query, the raccoon moves from town $1$ to town $4$. There is no prey anywhere, so output $-1$.
• In the $2$nd query, a prey animal of value $13$ appears in town $1$.
• In the $3$rd query, a prey animal of value $133$ appears in town $1$.
• In the $4$th query, a prey animal of value $1333$ appears in town $3$.
• In the $5$th query, the raccoon moves from town $1$ to town $2$. It can catch $1$ of the prey: those of values $13, 133$ in town $1$, or the one of value $1333$ in town $3$.
It catches the one with the maximum value among these, $1333$, so output $1333$. For example, it moves in the order $1 \to 2 \to 3 \to 4 \to 2$ as shown below.

• In the $6$th query, the raccoon moves from town $4$ to town $3$. There is prey in town $1$, but going from town $4$ to visit town $1$ and then moving to town $3$ would require using the same road more than once, so this is impossible. Output $-1$.
• In the $7$th query, the raccoon moves from town $4$ to town $1$. Of the prey of values $13, 133$ in town $1$, it catches the larger one, so output $133$.
  

4 3 7
1 2
2 3
2 4
2 1 2
1 1 13
1 1 133
1 3 1333
2 1 4
2 4 3
2 4 1

-1
133
1333
13