Вам дан неориентированный граф из \(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\)).
Выходные данные
На каждый запрос первого типа выведите одно целое число — значение \(p_u\), записанное в выбранной в запросе вершине \(u\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|