from heapq import heappop,heappush,heapify from collections import deque class Graph(): #non-directed def __init__(self,n,edge): self.n = n self.graph = [[] for _ in range(n)] self.deg = [0 for _ in range(n)] for e in edge: self.graph[e[0] - 1].append(e[1] - 1) self.graph[e[1] - 1].append(e[0] - 1) self.deg[e[0] - 1] += 1 self.deg[e[1] - 1] += 1 def lowlink(self): #DFS木, ord, lowを計算 self.ord = [None for _ in range(self.n)] self.low = [None for _ in range(self.n)] self.group = [None for _ in range(self.n)] self.prev = [None for _ in range(self.n)] self.tree = [[] for _ in range(self.n)] self.sorted = [] order = 0 count = 0 low = [None for _ in range(self.n)] for s in range(self.n): if self.group[s] is None: stack = [(s, None)] while stack: node, par = stack.pop() if self.group[node] is None: self.group[node] = count self.ord[node] = order self.sorted.append(node) order += 1 if par is not None: self.prev[node] = par self.tree[par].append(node) for adj in self.graph[node]: if self.group[adj] is None: stack.append((adj, node)) count += 1 for node in self.sorted[::-1]: self.low[node] = self.ord[node] for adj in self.graph[node]: if self.prev[adj] == node: self.low[node] = min(self.low[node], self.low[adj]) elif self.prev[node] == adj: continue else: self.low[node] = min(self.low[node], self.ord[adj]) def articulation(self): res = [] for node in range(self.n): if self.prev[node] is None and len(self.tree[node]) > 1: res.append(node) if self.prev[node] is not None: for adj in self.tree[node]: if self.ord[node] <= self.low[adj]: res.append(node) break return res def bridge(self): res = [] for node in range(self.n): for adj in self.tree[node]: if self.ord[node] < self.low[adj]: res.append((node, adj)) return res class Tree(): def __init__(self, n, edge): self.n = n self.tree = [[] for _ in range(n)] for e in edge: self.tree[e[0] - 1].append(e[1] - 1) self.tree[e[1] - 1].append(e[0] - 1) def setroot(self, root): self.root = root self.parent = [None for _ in range(self.n)] self.parent[root] = -1 self.depth = [None for _ in range(self.n)] self.depth[root] = 0 self.order = [] self.order.append(root) self.size = [1 for _ in range(self.n)] stack = [root] while stack: node = stack.pop() for adj in self.tree[node]: if self.parent[adj] is None: self.parent[adj] = node self.depth[adj] = self.depth[node] + 1 self.order.append(adj) stack.append(adj) for node in self.order[::-1]: for adj in self.tree[node]: if self.parent[node] == adj: continue self.size[node] += self.size[adj] def heavylight_decomposition(self): self.order = [None for _ in range(self.n)] self.head = [None for _ in range(self.n)] self.head[self.root] = self.root self.next = [None for _ in range(self.n)] stack = [self.root] order = 0 while stack: node = stack.pop() self.order[node] = order order += 1 maxsize = 0 for adj in self.tree[node]: if self.parent[node] == adj: continue if maxsize < self.size[adj]: maxsize = self.size[adj] self.next[node] = adj for adj in self.tree[node]: if self.parent[node] == adj or self.next[node] == adj: continue self.head[adj] = adj stack.append(adj) if self.next[node] is not None: self.head[self.next[node]] = self.head[node] stack.append(self.next[node]) def range_hld(self, u, v, edge=False): res = [] while True: if self.order[u] > self.order[v]: u, v = v, u if self.head[u] != self.head[v]: res.append((self.order[self.head[v]], self.order[v] + 1)) v = self.parent[self.head[v]] else: res.append((self.order[u] + edge, self.order[v] + 1)) return res def subtree_hld(self, u): return self.order[u], self.order[u] + self.size[u] def lca_hld(self, u, v): while True: if self.order[u] > self.order[v]: u, v = v, u if self.head[u] != self.head[v]: v = self.parent[self.head[v]] else: return u class SegmentTree(): def __init__(self, arr, func=min, ie=2**63): self.h = (len(arr) - 1).bit_length() self.n = 2**self.h self.ie = ie self.func = func self.tree = [ie for _ in range(2 * self.n)] for i in range(len(arr)): self.tree[self.n + i] = arr[i] for i in range(1, self.n)[::-1]: self.tree[i] = func(self.tree[2 * i], self.tree[2 * i + 1]) def set(self, idx, x): idx += self.n self.tree[idx] = x while idx: idx >>= 1 self.tree[idx] = self.func(self.tree[2 * idx], self.tree[2 * idx + 1]) def query(self, lt, rt): lt += self.n rt += self.n vl = vr = self.ie while rt - lt > 0: if lt & 1: vl = self.func(vl, self.tree[lt]) lt += 1 if rt & 1: rt -= 1 vr = self.func(self.tree[rt], vr) lt >>= 1 rt >>= 1 return self.func(vl, vr) import sys input = sys.stdin.readline INF = 10**18 N, M, Q = map(int, input().split()) edge = [tuple(map(int, input().split())) for _ in range(M)] g = Graph(N, edge) g.lowlink() bridge = set(g.bridge()) edge_no_bridge = [] for e in edge: if (e[0] - 1, e[1] - 1) in bridge or (e[1] - 1, e[0] - 1) in bridge: continue edge_no_bridge.append(e) graph_no_edge = Graph(N, edge_no_bridge) graph_no_edge.lowlink() decomposed = graph_no_edge.group count = max(decomposed) + 1 decomposed_to_node = [[] for _ in range(count)] for i in range(count): decomposed_to_node[decomposed[i]].append(i) branch = [] for a, b in bridge: branch.append((decomposed[a] + 1, decomposed[b] + 1)) t = Tree(count, branch) t.setroot(0) t.heavylight_decomposition() arr = [(-1, None) for _ in range(count)] st = SegmentTree(arr, max, (-1, None)) enemy = [[] for _ in range(count)] res = [] for _ in range(Q): q, x, y = map(int, input().split()) if q == 1: heappush(enemy[decomposed[x - 1]], -y) st.set(t.order[decomposed[x - 1]], (-enemy[decomposed[x - 1]][0], decomposed[x - 1])) else: tmp = (-1, None) for lt, rt in t.range_hld(decomposed[x - 1], decomposed[y - 1]): tmp = max(tmp, st.query(lt, rt)) value, idx = tmp res.append(value) if value != -1: if enemy[idx]: heappop(enemy[idx]) if enemy[idx]: st.set(t.order[idx], (-enemy[idx][0], idx)) else: st.set(t.order[idx], (-1, None)) print('\n'.join(map(str, res)))