D. Граф и запросы
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан неориентированный граф из $$$n$$$ вершин и $$$m$$$ ребер. Изначально в каждой вершине записано число: в вершине $$$i$$$ записано число $$$p_i$$$ (все $$$p_i$$$ — различные числа от $$$1$$$ до $$$n$$$).

Вы должны обработать $$$q$$$ запросов двух типов:

  • $$$1$$$ $$$v$$$ — среди всех вершин, достижимых из вершины $$$v$$$ по ребрам (включая саму вершину $$$v$$$), найти вершину $$$u$$$ с максимальным записанным в ней числом $$$p_u$$$, вывести $$$p_u$$$ и заменить $$$p_u$$$ на $$$0$$$;
  • $$$2$$$ $$$i$$$ — удалить $$$i$$$-е ребро из графа.

Обратите внимание, что в запросе первого типа может возникнуть такая ситуация, что во всех вершинах, достижимых из $$$v$$$, записано число $$$0$$$ — в таком случае вершина $$$u$$$ явно не определена, но так как от выбора конкретной вершины $$$u$$$ ничего не зависит, в ответ на такой запрос можно выбрать любую вершину, достижимую из $$$v$$$, и вывести число, записанное в ней (то есть $$$0$$$).

Входные данные

В первой строке заданы три целых числа $$$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$$$). Гарантируется, что на момент каждого запроса второго типа соответствующее ребро еще не удалено из графа.
Выходные данные

На каждый запрос первого типа выведите одно целое число — значение $$$p_u$$$, записанное в выбранной в запросе вершине $$$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