Codeforces Round 673 (Div. 1) |
---|
Finished |
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:
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$$$).
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:
For every query of the first type, print the value of $$$p_u$$$ written on the chosen vertex $$$u$$$.
5 4 6 1 2 5 4 3 1 2 2 3 1 3 4 5 1 1 2 1 2 3 1 1 1 2 1 2
5 1 2 0
Name |
---|