CF1416D.Graph and Queries

You are given an undirected graph consisting of $n$ vertices and $m$ edges. Initially there is a single integer written on every vertex: the vertex $i$ has $p_i$ written on it. All $p_i$ are distinct integers from $1$ to $n$.

You have to process $q$ queries of two types:

• $1$ $v$ — among all vertices reachable from the vertex $v$ using the edges of the graph (including the vertex $v$ itself), find a vertex $u$ with the largest number $p_u$ written on it, print $p_u$ and replace $p_u$ with $0$;
• $2$ $i$ — delete the $i$-th edge from the graph.

Note that, in a query of the first type, it is possible that all vertices reachable from $v$ have $0$ written on them. In this case, $u$ is not explicitly defined, but since the selection of $u$ does not affect anything, you can choose any vertex reachable from $v$ and print its value (which is $0$).

给你一个包含 $n$ 个顶点和 $m$ 条边的无向图。初始时，每个顶点上都写有一个整数：顶点 $i$ 上写有 $p_i$。所有 $p_i$ 均为 $1$ 到 $n$ 之间互不相同的整数。

你需要处理 $q$ 个查询，查询分为两类：

• $1$ $v$ — 在所有可通过图中的边从顶点 $v$ 到达的顶点（包括顶点 $v$ 本身）中，找出写有最大数值 $p_u$ 的顶点 $u$，输出 $p_u$，并将 $p_u$ 替换为 $0$；
• $2$ $i$ — 从图中删除第 $i$ 条边。

注意：对于第一类查询，有可能从 $v$ 可达的所有顶点上写的数均为 $0$。此时，$u$ 并未被明确定义；但由于 $u$ 的选取不影响任何结果，你可以任选一个从 $v$ 可达的顶点，并输出其值（即 $0$）。

The first line contains three integers $n$, $m$ and $q$ ($1 \le n \le 2 \cdot 10^5$; $1 \le m \le 3 \cdot 10^5$; $1 \le q \le 5 \cdot 10^5$).

The second line contains $n$ distinct integers $p_1$, $p_2$, ..., $p_n$, where $p_i$ is the number initially written on vertex $i$ ($1 \le p_i \le n$).

Then $m$ lines follow, the $i$-th of them contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$) and means that the $i$-th edge connects vertices $a_i$ and $b_i$. It is guaranteed that the graph does not contain multi-edges.

Then $q$ lines follow, which describe the queries. Each line is given by one of the following formats:

• $1$ $v$ — denotes a query of the first type with a vertex $v$ ($1 \le v \le n$).
• $2$ $i$ — denotes a query of the second type with an edge $i$ ($1 \le i \le m$). For each query of the second type, it is guaranteed that the corresponding edge is not deleted from the graph yet.

第一行包含三个整数 $n$、$m$ 和 $q$（$1 \le n \le 2 \cdot 10^5$；$1 \le m \le 3 \cdot 10^5$；$1 \le q \le 5 \cdot 10^5$）。

第二行包含 $n$ 个互不相同的整数 $p_1$, $p_2$, ..., $p_n$，其中 $p_i$ 表示顶点 $i$ 上初始写入的数字（$1 \le p_i \le n$）。

接下来是 $m$ 行，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$，$a_i \ne b_i$），表示第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。保证图中不含重边。

接下来是 $q$ 行，描述各查询。每行采用以下两种格式之一：

• $1$ $v$ — 表示类型一的查询，参数为顶点 $v$（$1 \le v \le n$）。
• $2$ $i$ — 表示类型二的查询，参数为边 $i$（$1 \le i \le m$）。对于每个类型二的查询，保证对应的边尚未从图中删除。

For every query of the first type, print the value of $p_u$ written on the chosen vertex $u$.

对于每个第一类查询，输出所选顶点 $u$ 上写的值 $p_u$。