import sys from collections import deque def hopcroft_karp(U_size, V_size, adj): pair_U = [0] * (U_size + 1) # Pair for spies (1-based) pair_V = [0] * (V_size + 1) # Pair for tasks (1-based) dist = [0] * (U_size + 1) # Distance for BFS layers def bfs(): queue = deque() for u in range(1, U_size + 1): if pair_U[u] == 0: dist[u] = 0 queue.append(u) else: dist[u] = float('inf') dist[0] = float('inf') # Dummy node while queue: u = queue.popleft() if dist[u] < dist[0]: for v in adj[u]: if dist[pair_V[v]] == float('inf'): dist[pair_V[v]] = dist[u] + 1 queue.append(pair_V[v]) return dist[0] != float('inf') def dfs(u): if u != 0: for v in adj[u]: if dist[pair_V[v]] == dist[u] + 1: if dfs(pair_V[v]): pair_U[u] = v pair_V[v] = u return True dist[u] = float('inf') return False return True result = 0 while bfs(): for u in range(1, U_size + 1): if pair_U[u] == 0: if dfs(u): result += 1 return pair_U, pair_V, result def kosaraju_scc(graph, num_nodes): visited = [False] * (num_nodes + 1) order = [] # First pass to get finishing order for node in range(1, num_nodes + 1): if not visited[node]: stack = [(node, False)] while stack: v, processed = stack.pop() if processed: order.append(v) continue if visited[v]: continue visited[v] = True stack.append((v, True)) for neighbor in reversed(graph[v]): if not visited[neighbor]: stack.append((neighbor, False)) # Build reversed graph reversed_graph = [[] for _ in range(num_nodes + 1)] for u in range(1, num_nodes + 1): for v in graph[u]: reversed_graph[v].append(u) # Second pass to get SCCs visited = [False] * (num_nodes + 1) scc_ids = [0] * (num_nodes + 1) component_id = 0 while order: node = order.pop() if not visited[node]: stack = [node] visited[node] = True component = [] while stack: v = stack.pop() component.append(v) for neighbor in reversed_graph[v]: if not visited[neighbor]: visited[neighbor] = True stack.append(neighbor) for v in component: scc_ids[v] = component_id component_id += 1 return scc_ids def main(): input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]); ptr +=1 M = int(input[ptr]); ptr +=1 L = int(input[ptr]); ptr +=1 adj = [[] for _ in range(N+1)] # adj[u] contains tasks (v) that u can do edges = [] for _ in range(L): S = int(input[ptr]); ptr +=1 T = int(input[ptr]); ptr +=1 adj[S].append(T) edges.append((S, T)) # Compute maximum matching pair_U, pair_V, max_matching = hopcroft_karp(N, M, adj) # Build residual graph total_nodes = N + M residual_graph = [[] for _ in range(total_nodes +1)] # 1-based for S, T in edges: # For each edge (S, T) # Check if it's matched if pair_U[S] == T: # Matched edge: task T → spy S in residual residual_graph[N + T].append(S) else: # Unmatched edge: spy S → task T in residual residual_graph[S].append(N + T) # Compute SCCs scc_ids = kosaraju_scc(residual_graph, total_nodes) # Process each edge for S, T in edges: if pair_U[S] == T: # Check if S (spy node) and T's node (N + T) are in the same SCC spy_node = S task_node = N + T if scc_ids[spy_node] == scc_ids[task_node]: print("Yes") else: print("No") else: # Unused edge, answer is Yes print("Yes") if __name__ == "__main__": main()