class Graph: __slots__=("edge_offset", "edge_alive", "edge_ids", "vertex_alive", "adjacent", "deg") #入力定義 def __init__(self, N = 0, edge_offset = 0): """ N 頂点の空グラフ (多重辺なし) を生成する.""" self.adjacent = [[] for _ in range(N)] self.edge_ids = [[] for _ in range(N)] self.vertex_alive = [1] * N self.edge_offset = edge_offset self.edge_alive = [0] * edge_offset self.deg = [0] * N #頂点の追加 def add_vertex(self): """ 頂点を追加する. """ self.adjacent.append([]) self.edge_ids.append([]) self.vertex_alive.append(1) self.deg.append(0) return self.order() - 1 def add_vertices(self, k): """ 頂点を k 個追加する. k: int """ n=self.order() self.adjacent.extend([[] for _ in range(k)]) self.edge_ids.extend([[] for _ in range(k)]) self.vertex_alive.extend([1] * k) self.deg.extend([0] * k) return list(range(n, n + k)) #辺の追加 def add_edge(self, u, v): """ 無向辺 uv を加える""" j = len(self.edge_alive) self.adjacent[u].append(v) self.adjacent[v].append(u) self.edge_ids[u].append(j) self.edge_ids[v].append(j) self.deg[u] += 1; self.deg[v] += 1 self.edge_alive.append(1) return j #辺を除く def remove_edge(self,u,v): """ 無向辺 uv が存在するならば除く""" pass def reset_vertex(self, u): """ 頂点 u に接続している辺を全て消す.""" pass #Walkの追加 def add_walk(self, *walk): """ walk=(w[0],...,w[n-1]) に対して, n-1 本の辺 w[i]w[i+1] を加える.""" for i in range(len(walk) - 1): self.add_edge(walk[i], walk[i + 1]) #Cycleの追加 def add_cycle(self, *cycle): """ cycle=(c[0], ..., c[n-1]) を加える. """ self.add_walk(*cycle) self.add_edge(cycle[-1], cycle[0]) #グラフに辺が存在するか否か def edge_exist(self, u, v): """ 辺 uv が存在するか? """ pass def partner(self, v): adj = self.adjacent[v] edge_ids = self.edge_ids[v] return [adj[k] for k in range(len(edge_ids)) if self.edge_alive[edge_ids[k]]] def partner_with_index(self, v): adj = self.adjacent[v] edge_ids = self.edge_ids[v] return [(adj[k], edge_ids[k]) for k in range(len(edge_ids)) if self.edge_alive[edge_ids[k]]] #近傍 def neighborhood(self, v): """ 頂点 v の近傍を求める. """ adj = self.adjacent[v] edge_ids = self.edge_ids[v] return list(set(adj[k] for k in range(len(edge_ids)) if self.edge_alive[edge_ids[k]])) #次数 def degree(self, v): """ 頂点 v の次数を求める. """ return self.deg[v] #頂点数 def vertex_count(self): """ グラフの頂点数 (位数) を出力する. """ return len(self.adjacent) def order(self): """ グラフの位数 (頂点数) を出力する. """ return len(self.adjacent) #辺数 def edge_count(self): """ 辺の本数 (サイズ) を出力する.""" return len(self.edge_alive) - self.edge_offset def size(self): """ サイズ (辺の本数) を出力する. """ return len(self.edge_alive) - self.edge_offset #頂点vを含む連結成分 def connected_component(self, v): """ 頂点 v を含む連結成分を出力する.""" N = self.order() stack = [v] comp = [0] * N; comp[v] = 1 while stack: x = stack.pop() for y in self.neighborhood(x): if comp[y] == 0: comp[y] = 1 stack.append(y) return [x for x in range(N) if comp[x]] #距離 def distance(self, u, v, default): """ 2頂点 u,v 間の距離を求める.""" if u == v: return 0 from collections import deque N = self.order() dist = [-1] * N; dist[u]=0 queue = deque([u]) while queue: x = queue.popleft() for y in self.neighborhood(x): if dist[y] == -1: dist[y] = dist[x] + 1 queue.append(y) if y == v: return dist[v] return default #ある1点からの距離 def distance_all(self,u,default=-1): """ 頂点 u からの距離を求める.""" from collections import deque N = self.order() dist = [-1] * N; dist[u]=0 queue = deque([u]) while queue: x = queue.popleft() for y in self.neighborhood(x): if dist[y] == -1: dist[y] = dist[x] + 1 queue.append(y) return [dist[x] if dist[x] != -1 else default for x in range(N)] #最短路 def shortest_path(self, u, v): """ u から v への最短路を求める (存在しない場合は None). """ if u == v: return [u] from collections import deque prev = [-1] * self.order() prev[u] = u queue = deque([u]) while queue: x = queue.popleft() for y in self.adjacent[x]: if prev[x] != -1: continue prev[y] = x queue.append(y) if y != v: continue path = [v] a = v while a != u: a = prev[a] path.append(a) return path[::-1] return None def edge_yielder(self): u = [0] * len(self.edge_alive); v = [0] * len(self.edge_alive) for x in range(self.order()): adj = self.adjacent[x] ids = self.edge_ids[x] for k in range(len(adj)): id = ids[k] u[id] = min(x, adj[k]) v[id] = max(x, adj[k]) for id in range(len(self.edge_alive)): if self.edge_alive[id]: yield (u[id], v[id]) def edge_yielder_with_index(self): u = [0] * len(self.edge_alive); v = [0] * len(self.edge_alive) for x in range(self.order()): adj = self.adjacent[x] ids = self.edge_ids[x] for k in range(len(adj)): id = ids[k] u[id] = min(x, adj[k]) v[id] = max(x, adj[k]) for id in range(len(self.edge_alive)): if self.edge_alive[id]: yield (id, u[id], v[id]) def Lowlink(G: Graph, mode=0): """ G の ord, lowlink を求める. G: Graph output: (ord, lowlink) """ from collections import deque N=G.vertex_count() ord=[-1]*N; low=[-1]*N flag=[0]*N adj=G.adjacent parent=[-1]*N #BFSパート for v in range(N): if flag[v]: continue k=0 S=deque([v]) T=[] while S: u=S.pop() if flag[u]: continue T.append(u) ord[u]=k k+=1 flag[u]=1 for w in G.neighborhood(u): if not flag[w]: S.append(w) parent[w]=u for u in T: low[u]=ord[u] for w in T[:0:-1]: for x in adj[w]: if w==v or x!=parent[w]: low[w]=min(low[w],low[x],ord[x]) if mode==0: return ord, low else: return ord, low, parent #橋列挙 def Bridge(G: Graph): """ G にある橋の id を列挙する. G: Graph """ ord, low = Lowlink(G) return [id for id, u, v in G.edge_yielder_with_index() if (ord[u] < low[v]) or (ord[v] < low[u])] #連結成分に分解 def Connected_Component_Decomposition(G: Graph, mode = 0): """ 連結成分毎に分解する. G: Graph mode:0 → 連結成分, 1 → 連結成分番号, 2 → (連結成分, 連結成分番号)""" comp_id = [-1] * G.order() comps = [] def dfs(start, id): stack = [start] comp_id[start] = id comp = [] while stack: x = stack.pop() comp.append(x) for y in G.neighborhood(x): if comp_id[y] == -1: comp_id[y] = id stack.append(y) comps.append(comp) id = 0 for x in range(G.order()): if comp_id[x] == -1: dfs(x, id) id += 1 if mode == 0: return comps elif mode == 1: return comp_id elif mode == 2: return (comps, comp_id) #================================================== def solve(): N, M, Q = map(int, input().split()) G = Graph(N + 1) for j in range(M): u, v = map(int, input().split()) G.add_edge(u, v) bridges = set(Bridge(G)) H = Graph(N + 1) for j, u, v in G.edge_yielder_with_index(): if j in bridges: H.add_edge(u, v) comp_id = Connected_Component_Decomposition(H, 1) ans = [False] * Q for q in range(Q): x, y = map(int, input().split()) ans[q] = (comp_id[x] == comp_id[y]) return ans #================================================== import sys input=sys.stdin.readline write=sys.stdout.write write("\n".join(map(str, ["Yes" if ans else "No" for ans in solve()])))