import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Comparator; import java.util.PriorityQueue; import java.util.Scanner; class Main implements Runnable { public static void main(String[] args) { new Thread(null, new Main(), "", Runtime.getRuntime().maxMemory()).start(); } class State { int i; int parent; int j;// 操作後g[i][j]に潜る public State(int i_, int parent_, int j_) { i = i_; parent = parent_; j = j_; } } int two_edge_connected_componets(ArrayList[] g, int[] col) { int n = g.length; Arrays.fill(col, -1); int cols = 0; int[] low = new int[n]; int[] ord = new int[n]; boolean[] marked = new boolean[n]; Arrays.fill(low, -1); Arrays.fill(ord, -1); int order = 0; ArrayDeque stk = new ArrayDeque<>(); ArrayDeque pnd = new ArrayDeque<>(); for (int ii = 0; ii < n; ++ii) { if (ord[ii] == -1) { stk.add(new State(ii, -1, 0)); } while (!stk.isEmpty()) { State s = stk.pollFirst(); if (ord[s.i] == -1) { low[s.i] = (ord[s.i] = order++); pnd.addFirst(s.i); } if (s.j > 0 && s.parent != g[s.i].get(s.j - 1) && !marked[g[s.i].get(s.j - 1)]) { if (low[g[s.i].get(s.j - 1)] == -1) { throw new AssertionError(); } low[s.i] = Math.min(low[s.i], low[g[s.i].get(s.j - 1)]); } if (s.j == g[s.i].size() && low[s.i] == ord[s.i]) { while (true) { int v = pnd.pollFirst(); col[v] = cols; marked[v] = true; if (v == s.i) break; } ++cols; continue; } if (s.j == g[s.i].size()) continue; int v = g[s.i].get(s.j); stk.addFirst(new State(s.i, s.parent, s.j + 1)); if (ord[v] == -1) { stk.addFirst(new State(v, s.i, 0)); } else if (v != s.parent && !marked[v]) { low[s.i] = Math.min(low[s.i], low[v]); } } } return cols; } @SuppressWarnings("unchecked") public void run() { Scanner sc = new Scanner(System.in); PrintWriter pw = new PrintWriter(System.out); int n = sc.nextInt(); int m = sc.nextInt(); int q = sc.nextInt(); ArrayList[] g = new ArrayList[n]; for (int i = 0; i < n; ++i) { g[i] = new ArrayList<>(); } for (int i = 0; i < m; ++i) { int a = sc.nextInt() - 1; int b = sc.nextInt() - 1; g[a].add(b); g[b].add(a); } int[] col = new int[n]; int cols = two_edge_connected_componets(g, col); ArrayList[] h = new ArrayList[cols]; PriorityQueue[] w = new PriorityQueue[cols]; for (int i = 0; i < cols; ++i) { w[i] = new PriorityQueue<>(new Comparator() { @Override public int compare(Long o1, Long o2) { return -Long.compare(o1, o2); } }); } for (int i = 0; i < cols; ++i) { w[i].add(-1L); } for (int i = 0; i < cols; ++i) { h[i] = new ArrayList<>(); } for (int i = 0; i < n; ++i) { for (int j : g[i]) { int a = col[i]; int b = col[j]; if (a == b) continue; if (h[a].contains(b)) continue; h[a].add(b); h[b].add(a); } } for (int i = 0; i < cols; ++i) { Collections.sort(h[i]); for (int j = 0; j < h[i].size(); ++j) { while (j + 1 < h[i].size() && h[i].get(j) == h[i].get(j + 1)) { h[i].remove(j + 1); } } } HLDecomposition hl = new HLDecomposition(n); for (int i = 0; i < cols; ++i) { for (int j : h[i]) { if (i > j) { hl.ae(i, j); } } } hl.pre(); SegmentTree st = new SegmentTree(n); int[] ref = new int[cols]; Arrays.fill(ref, -1); for (int i = 0; i < cols; ++i) { ref[hl.id[i]] = i; } while (q-- > 0) { int t = sc.nextInt(); if (t == 1) {// modification query int u = sc.nextInt() - 1; long v = sc.nextInt(); u = col[u]; w[u].add(v); st.setVal(hl.id[u], w[u].peek()); } else {// ouput query int src = sc.nextInt() - 1; int dst = sc.nextInt() - 1; src = col[src]; dst = col[dst]; V v = output(src, dst, hl, st); System.out.println(v.v); if (v.v != -1) { w[ref[v.id]].poll(); st.setVal(v.id, w[ref[v.id]].peek()); } } } pw.close(); } V output(int a, int b, HLDecomposition hl, SegmentTree st) { V ea = new V(-1, -1); V eb = new V(-1, -1); while (hl.head[a] != hl.head[b]) { if (hl.depth[hl.head[a]] < hl.depth[hl.head[b]]) { int tmp = a; a = b; b = tmp; V tmp_e = new V(ea.v, ea.id); ea = eb; eb = tmp_e; } ea = merge(st.query(hl.id[hl.head[a]], hl.id[a] + 1), ea); a = hl.parent[hl.head[a]]; } if (hl.depth[a] < hl.depth[b]) { int tmp = a; a = b; b = tmp; V tmp_e = new V(ea.v, ea.id); ea = eb; eb = tmp_e; } return merge(eb, merge(st.query(hl.id[b], hl.id[a] + 1), ea)); } class V { long v; int id; public V(long v_, int id_) { v = v_; id = id_; } } V merge(V a, V b) { if (a.v < b.v) { return b; } else { return a; } } class SegmentTree { int n; V[] Vs; public SegmentTree(int n_) { n = 1; while (n < n_) { n *= 2; } Vs = new V[2 * n - 1]; for (int i = 0; i < n; ++i) { Vs[i + n - 1] = new V(-1, i); } for (int i = n - 2; i >= 0; --i) { Vs[i] = merge(Vs[2 * i + 1], Vs[2 * i + 2]); } } void setVal(int k, long val) { k += n - 1; Vs[k] = new V(val, k - (n - 1)); while (k > 0) { k = (k - 1) / 2; Vs[k] = merge(Vs[2 * k + 1], Vs[2 * k + 2]); } } // [a,b),[l,r) V query(int a, int b) { return query(a, b, 0, n, 0); } V query(int a, int b, int l, int r, int k) { if (b <= l || r <= a) { return new V(-1, -1); } if (a <= l && r <= b) { return Vs[k]; } else { V vl = query(a, b, l, (l + r) / 2, 2 * k + 1); V vr = query(a, b, (l + r) / 2, r, 2 * k + 2); return merge(vl, vr); } } } class HLDecomposition { int n; int[] depth; int[] head; int[] heavy; int[] parent; int[] sz; ArrayList[] g; int[] id; @SuppressWarnings("unchecked") public HLDecomposition(int n) { this.n = n; depth = new int[n]; head = new int[n]; heavy = new int[n]; parent = new int[n]; id = new int[n]; sz = new int[n]; g = new ArrayList[n]; for (int i = 0; i < n; ++i) { g[i] = new ArrayList<>(); } Arrays.fill(head, -1); Arrays.fill(id, -1); Arrays.fill(parent, -1); } void ae(int a, int b) { g[a].add(b); g[b].add(a); } void pre() { dfs(0, -1); bfs(); } void bfs() { ArrayDeque pend = new ArrayDeque<>(); int gen = 0; pend.add(0); while (!pend.isEmpty()) { int v = pend.pollFirst(); int top = v; for (; v != -1; v = heavy[v]) { id[v] = gen++; head[v] = top; for (int d : g[v]) { if (d == parent[v] || d == heavy[v]) { continue; } pend.add(d); } } } } int lca(int u, int v) { if (head[u] != head[v]) { if (depth[head[u]] < depth[head[v]]) { int tmp = u; u = v; v = tmp; } return lca(parent[head[u]], v); } else { if (depth[u] > depth[v]) { int tmp = u; u = v; v = tmp; } return u; } } int dfs(int c, int p) { parent[c] = p; int s = 1; int to = -1; for (int d : g[c]) { if (d == p) continue; depth[d] = depth[c] + 1; s += dfs(d, c); if (to == -1 || sz[d] > sz[to]) { to = d; } } sz[c] = s; heavy[c] = to; return s; } } static void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } }