import java.util.*; import java.util.function.*; class HLDecomposition { int[] p; ArrayList[] child; int[] weight; boolean[] isHeavy; int[] heavyChild; int[] root; int[] vertexId; int[] invVertexId; void dfs(int v) { int total = 1; for (int w: this.child[v]) { dfs(w); total += this.weight[w]; } this.weight[v] = total; int maxi = -1; int ma = 0; for (int w: this.child[v]) { if (ma < weight[w]) { maxi = w; ma = weight[w]; } } if (maxi >= 0) { this.isHeavy[maxi] = true; this.heavyChild[v] = maxi; } } void dfs2(int v, int root) { this.root[v] = root; for (int w: this.child[v]) { if (isHeavy[w]) { dfs2(w, root); } else { dfs2(w, w); } } } void bfs() { int n = this.p.length; Queue queue = new ArrayDeque(); queue.add(0); int count = 0; while (queue.size() >= 1) { int current = queue.poll(); for (; current != -1; current = this.heavyChild[current]) { for (int target: this.child[current]) { if (this.heavyChild[current] != target) { queue.add(target); } } this.vertexId[current] = count; count++; } } if (count != n) { throw new RuntimeException(); } for (int i = 0; i < n; ++i) { this.invVertexId[this.vertexId[i]] = i; } } @SuppressWarnings("unchecked") HLDecomposition(int[] p) { this.p = Arrays.copyOf(p, p.length); int n = this.p.length; if (n >= 1 << 18) { throw new RuntimeException(); } this.child = new ArrayList[n]; for (int i = 0; i < n; ++i) { this.child[i] = new ArrayList(); } this.weight = new int[n]; this.isHeavy = new boolean[n]; this.heavyChild = new int[n]; this.root = new int[n]; this.vertexId = new int[n]; this.invVertexId = new int[n]; Arrays.fill(this.isHeavy, false); Arrays.fill(this.heavyChild, -1); for (int i = 1; i < n; ++i) { this.child[p[i]].add(i); } dfs(0); dfs2(0, 0); bfs(); } @FunctionalInterface static interface QueryFunction { public abstract void apply(int a, int b, int id, boolean reversed); } void decomposeSub(int s, int t, int start, int end, QueryFunction op) { if (start >= end) { throw new RuntimeException(); } if (this.vertexId[s] > this.vertexId[t]) { op.apply(Math.max(this.vertexId[this.root[s]], this.vertexId[t]), this.vertexId[s], start, true); if (this.root[s] != this.root[t]) { decomposeSub(this.p[this.root[s]], t, start + 1, end, op); } } else { op.apply(Math.max(this.vertexId[this.root[t]], this.vertexId[s]), this.vertexId[t], end, false); if (this.root[s] != this.root[t]) { decomposeSub(s, this.p[this.root[t]], start, end - 1, op); } } } List decomposePath(int s, int t) { List list = new ArrayList(); decomposeSub(s, t, 0, 100, (int x, int y, int id, boolean reversed) -> { list.add((long) id << 37 | (long) x << 19 | (long) y << 1 | (reversed ? 1 : 0)); }); return list; } } class TwoEdgeComponent { ArrayList[] graph; int[] order, lowlink; int count; int[] comp; boolean[] visited; int[] tree; boolean dfs(int v) { return dfs(v, -1); } boolean dfs(int v, int par) { if (this.order[v] >= 0) { return false; } this.order[v] = count; count++; int lowlink = this.order[v]; for (int w: this.graph[v]) { if (par == w) { continue; } boolean result = dfs(w, v); if (result) { lowlink = Math.min(lowlink, this.lowlink[w]); } else { lowlink = Math.min(lowlink, this.order[w]); } } this.lowlink[v] = lowlink; return true; } void dfs2(int v, int par, int compId) { if (this.visited[v]) { return; } this.visited[v] = true; if (par >= 0 && this.order[par] < this.lowlink[v]) { // Hasi compId = this.count; this.count++; this.tree[compId] = this.comp[par]; } this.comp[v] = compId; for (int w: this.graph[v]) { dfs2(w, v, compId); } } TwoEdgeComponent(ArrayList[] graph) { int n = graph.length; this.graph = graph; this.order = new int[n]; this.lowlink = new int[n]; Arrays.fill(this.order, -1); Arrays.fill(this.lowlink, -1); this.count = 0; dfs(0); this.count = 1; this.comp = new int[n]; this.visited = new boolean[n]; this.tree = new int[n]; Arrays.fill(this.tree, -1); dfs2(0, -1, 0); } public static int[] solve(ArrayList[] graph, int[] array) { TwoEdgeComponent comp = new TwoEdgeComponent(graph); for (int i = 0; i < graph.length; ++i) { array[i] = comp.comp[i]; } return Arrays.copyOfRange(comp.tree, 0, comp.count); } } class SegmentTree { static final int SIZE = 1 << 18; long[] seg; SegmentTree() { this.seg = new long[2 * SIZE]; } void update(int x, long value) { x += SIZE - 1; this.seg[x] = value; while (x > 0) { x = (x - 1) / 2; this.seg[x] = Math.max(this.seg[2 * x + 1], this.seg[2 * x + 2]); } } long query(int l, int r) { l += SIZE - 1; r += SIZE - 1; long y = Long.MIN_VALUE; while (l < r) { if ((l & 1) == 0) { y = Math.max(y, this.seg[l]); } if ((r & 1) == 0) { y = Math.max(y, this.seg[r - 1]); } l /= 2; r = (r - 1) / 2; } return y; } } class Main implements Runnable { // https://qiita.com/p_shiki37/items/a0f6aac33bf60f5f65e4#%E3%82%B9%E3%82%BF%E3%83%83%E3%82%AF%E3%81%AE%E6%8B%A1%E5%BC%B5 public static void main(String[] args) { new Thread(null, new Main(), "", 128 * 1024 * 1024).start(); //16MBスタックを確保して実行 } @SuppressWarnings("unchecked") public void run() { Scanner scan = new Scanner(System.in); int n = Integer.parseInt(scan.next()); int m = Integer.parseInt(scan.next()); int q = Integer.parseInt(scan.next()); ArrayList[] graph = new ArrayList[n]; for (int i = 0; i < n; ++i) { graph[i] = new ArrayList(); } for (int i = 0; i < m; ++i) { int a = Integer.parseInt(scan.next()) - 1; int b = Integer.parseInt(scan.next()) - 1; graph[a].add(b); graph[b].add(a); } int[] comp = new int[n]; int[] tree = TwoEdgeComponent.solve(graph, comp); int treeN = tree.length; HLDecomposition hlDecomp = new HLDecomposition(tree); PriorityQueue[] queues = new PriorityQueue[treeN]; SegmentTree seg = new SegmentTree(); for (int i = 0; i < treeN; ++i) { queues[i] = new PriorityQueue((Long x, Long y) -> y.compareTo(x)); queues[i].add(-1L); // banpei seg.update(i, -1); } for (int i = 0; i < q; ++i) { int kind = Integer.parseInt(scan.next()); if (kind == 1) { int u = Integer.parseInt(scan.next()) - 1; int w = Integer.parseInt(scan.next()); int compId = comp[u]; queues[compId].add((long) w << 32 | compId); seg.update(hlDecomp.vertexId[compId], queues[compId].peek()); } else { int s = Integer.parseInt(scan.next()) - 1; int t = Integer.parseInt(scan.next()) - 1; List paths = hlDecomp.decomposePath(comp[s], comp[t]); long maximum = -1; for (long crypt: paths) { int id = (int) (crypt >> 37); int l = (int) (crypt >> 19) & 0x3ffff; int r = (int) (crypt >> 1) & 0x3ffff; boolean reversed = crypt % 2 == 1; maximum = Math.max(maximum, seg.query(l, r + 1)); } if (maximum == -1) { // Dare mo inai System.out.println(-1); continue; } int value = (int) (maximum >>> 32); int id = (int) maximum; assert queues[id].peek() == maximum; System.out.println(value); queues[id].poll(); assert queues[id].size() >= 1; seg.update(hlDecomp.vertexId[id], queues[id].peek()); } } } }