import sys # Increase recursion depth limit for deep structures like MST potentially # Needs to be large enough for N=200000. Python default is often 1000. # Set it to slightly more than max N + M maybe, though N vertices dominate depth. sys.setrecursionlimit(200000 + 50) def solve(): N, M = map(int, sys.stdin.readline().split()) # Store edge information. We'll need edge index (1-based) and its endpoints. edges_info = [] # Stores dict for each edge: u, v, id # Map edge ID (1-based) to its information dict for quick lookup later edge_map_by_id = {} for i in range(M): u, v = map(int, sys.stdin.readline().split()) # Store edge data. Weight 2^id calculation will be done on the fly when needed. edge_data = { 'u': u, 'v': v, 'id': i + 1} edges_info.append(edge_data) edge_map_by_id[i + 1] = edge_data # --- Kruskal's Algorithm to build Minimum Spanning Tree (MST) --- # Use Disjoint Set Union (DSU) data structure. parent_dsu = list(range(N + 1)) def find_set(v): # Path compression heuristic if v == parent_dsu[v]: return v parent_dsu[v] = find_set(parent_dsu[v]) return parent_dsu[v] def unite_sets(a, b): a = find_set(a) b = find_set(b) if a != b: # Basic union (no rank/size optimization, usually sufficient) parent_dsu[b] = a return True return False # Build MST adjacency list and identify non-MST edges mst_adj = [[] for _ in range(N + 1)] # Use list for adjacency list: node -> list of {'to': neighbor, 'id': edge_id} non_mst_edges_idx = [] # List of 0-based indices of edges NOT in MST mst_edge_ids = set() # Store IDs of edges that are part of the MST for quick check # Edges are implicitly sorted by index 1 to M, which corresponds to weights 2^1 to 2^M for i in range(M): edge_data = edges_info[i] u, v = edge_data['u'], edge_data['v'] if unite_sets(u, v): # Edge is part of MST mst_edge_ids.add(edge_data['id']) # Add edge to MST adjacency list for both endpoints mst_adj[u].append({'to': v, 'id': edge_data['id']}) mst_adj[v].append({'to': u, 'id': edge_data['id']}) else: # Edge creates a cycle, not part of MST non_mst_edges_idx.append(i) # --- Precomputation for path queries on MST using Binary Lifting --- MAX_LOG_N = (N).bit_length() # Maximum power of 2 needed for binary lifting, depends on N # Binary lifting tables # parent_binlift[node][k] = (ancestor_at_2^k_distance, edge_id_to_parent_at_2^0) # Note: edge_id is only stored for k=0 (direct parent) parent_binlift = [[(0, 0)] * MAX_LOG_N for _ in range(N + 1)] depth = [-1] * (N + 1) # Store depth of each node from root # path_xor_sum_binlift[node][k] stores the XOR sum of 2^edge_id for edges on the path from node to its 2^k ancestor path_xor_sum_binlift = [[0] * MAX_LOG_N for _ in range(N + 1)] # Python's arbitrary precision integers handle large XOR sums # Use BFS to initialize level 0 of binary lifting tables and depths # Assume graph is connected and vertex 1 exists. Root the MST at vertex 1. q = [(1, 0, 0)] # Queue stores (current_node, parent_node, depth) depth[1] = 0 head = 0 # processed_nodes_order = [] # Not strictly needed, can build tables directly in BFS/DFS while head < len(q): curr, p, d = q[head] head += 1 # processed_nodes_order.append(curr) # Optional: for ordered processing later # Iterate through neighbors in MST adjacency list for edge in mst_adj[curr]: neighbor = edge['to'] edge_id = edge['id'] if neighbor != p: # Avoid going back to parent # If neighbor hasn't been visited yet if depth[neighbor] == -1: depth[neighbor] = d + 1 # Set direct parent (k=0 level) parent_binlift[neighbor][0] = (curr, edge_id) # Set path XOR sum for edge to direct parent # The weight is 2^edge_id. In Python, left shift `1 << k` computes 2^k. path_xor_sum_binlift[neighbor][0] = (1 << edge_id) q.append((neighbor, curr, d + 1)) # Compute full binary lifting tables (levels 1 to MAX_LOG_N-1) for i in range(1, MAX_LOG_N): for node in range(1, N + 1): # Get the 2^(i-1) ancestor p_node, _ = parent_binlift[node][i-1] if p_node != 0: # If the ancestor exists # Get the 2^(i-1) ancestor of the ancestor (which is the 2^i ancestor) pp_node, _ = parent_binlift[p_node][i-1] if pp_node != 0: # If the 2^i ancestor exists # Store the 2^i ancestor. Edge ID is irrelevant here. parent_binlift[node][i] = (pp_node, 0) # Compute path XOR sum using values from level i-1 path_xor_sum_binlift[node][i] = path_xor_sum_binlift[node][i-1] ^ path_xor_sum_binlift[p_node][i-1] # --- Helper functions for LCA and path XOR sum --- # Find Lowest Common Ancestor (LCA) of two nodes u, v def get_lca(u, v): # Ensure u is the deeper node if depth[u] < depth[v]: u, v = v, u # Lift node u up to the same depth as v for i in range(MAX_LOG_N - 1, -1, -1): # If 2^i step doesn't go above v's depth if depth[u] - (1 << i) >= depth[v]: u = parent_binlift[u][i][0] # If u and v are now the same node, it's the LCA if u == v: return u # Lift u and v simultaneously until their parents are the same for i in range(MAX_LOG_N - 1, -1, -1): p_u, _ = parent_binlift[u][i] p_v, _ = parent_binlift[v][i] # Check if parents exist and are different if p_u != p_v: u = p_u v = p_v # The LCA is the direct parent of the current u (or v) return parent_binlift[u][0][0] # Calculate XOR sum of 2^edge_id for path from node u up to target_ancestor def get_path_xor_sum(u, target_ancestor): res = 0 target_depth = depth[target_ancestor] # Lift u step-by-step using binary lifting powers for i in range(MAX_LOG_N - 1, -1, -1): # If taking a 2^i step doesn't go above the target ancestor's depth if depth[u] - (1 << i) >= target_depth: # XOR the path sum for this segment res ^= path_xor_sum_binlift[u][i] # Move u up u = parent_binlift[u][i][0] return res # --- Precompute Cycle Information for Non-MST Edges --- # V_k stores the XOR sum L(C_k) for the cycle C_k formed by non-MST edge k # L(C_k) = 2^k XOR L(P''_{MST,k}), where P''_{MST,k} is the path in MST between endpoints of edge k. V_k = {} # Map: 0-based index k_idx -> BigInt value V_k for k_idx in non_mst_edges_idx: edge_data = edges_info[k_idx] p, q = edge_data['u'], edge_data['v'] edge_id = edge_data['id'] # 1-based ID lca = get_lca(p, q) # Calculate XOR sum of MST path between p and q path_xor = get_path_xor_sum(p, lca) ^ get_path_xor_sum(q, lca) # Calculate V_k value using the cycle property V_k[k_idx] = (1 << edge_id) ^ path_xor # --- Precompute DFS start/end times for subtree checks --- # Needed to efficiently check if an edge is on a path between two nodes timer = 0 tin = [-1] * (N + 1) # Stores entry time of DFS tout = [-1] * (N + 1) # Stores exit time of DFS # Use iterative DFS to avoid deep recursion issues dfs_stack = [(1, 0, 'enter')] # Stack stores (node, parent, state) state='enter' or 'exit' while dfs_stack: u, p, state = dfs_stack.pop() if state == 'enter': timer += 1 tin[u] = timer dfs_stack.append((u, p, 'exit')) # Schedule exit processing for this node # Explore neighbors in MST for edge in mst_adj[u]: neighbor = edge['to'] if neighbor != p: # Push neighbor onto stack for processing dfs_stack.append((neighbor, u, 'enter')) elif state == 'exit': # Process node upon exiting its subtree timer += 1 tout[u] = timer # Check if node u is an ancestor of node v using DFS times def is_ancestor(u, v): # Handle cases where nodes might not have been visited (e.g. disconnected graph, though problem says connected) if tin[u] == -1 or tin[v] == -1: return False # Standard check using entry and exit times return tin[u] <= tin[v] and tout[u] >= tout[v] # --- Precompute powers of 2 modulo MOD --- MOD = 10**9 + 7 P2 = [1] * (M + 1) # P2[i] stores 2^i mod MOD for i in range(1, M + 1): P2[i] = (P2[i-1] * 2) % MOD # Function to calculate the final path sum modulo MOD from its XOR sum representation def get_mod_sum(xor_val): res = 0 # Iterate through bits potentially up to M. Max possible edge ID is M. Weight is 2^M. # Need to check bits up to M. # A path sum can exceed 2^M, but individual weights are 2^i for i<=M. # Determine appropriate bit length, M+1 is safe. Or dynamically check xor_val.bit_length(). max_bits = M + 1 if xor_val > 0: max_bits = xor_val.bit_length() for i in range(max_bits): # If the i-th bit is set in the XOR sum if (xor_val >> i) & 1: # Add the corresponding power of 2 (mod MOD) # Check if index i is valid (<= M) if i <= M: res = (res + P2[i]) % MOD return res # --- Process Queries --- Q = int(sys.stdin.readline()) results = [] # Store results for each query for _ in range(Q): x, y, z_id = map(int, sys.stdin.readline().split()) # Find LCA of query nodes x, y lca_xy = get_lca(x, y) # Calculate XOR sum of the MST path between x and y current_path_xor_sum = get_path_xor_sum(x, lca_xy) ^ get_path_xor_sum(y, lca_xy) # Check if the forbidden edge z_id is on the MST path between x and y is_z_on_path = False if z_id in mst_edge_ids: # Check if z_id is even part of the MST # Determine which endpoint is child (u) and which is parent (v) for edge z_id z_edge_info = edge_map_by_id[z_id] zu, zv = z_edge_info['u'], z_edge_info['v'] u_for_z, v_for_z = -1, -1 # u: child, v: parent # Check depth to identify parent-child relationship if depth[zu] > depth[zv]: u_for_z, v_for_z = zu, zv elif depth[zv] > depth[zu]: u_for_z, v_for_z = zv, zu # Verify this edge is indeed the one connecting u_for_z and v_for_z in MST if u_for_z != -1 and parent_binlift[u_for_z][0] == (v_for_z, z_id): # Check if z_id lies on the path x <-> y using LCA and subtree properties if is_ancestor(lca_xy, v_for_z): # LCA of x,y must be ancestor of parent endpoint v # Check if x and y are separated by the edge z_id is_x_in_subtree = is_ancestor(u_for_z, x) # Is x in subtree of child u? is_y_in_subtree = is_ancestor(u_for_z, y) # Is y in subtree of child u? # If one is in subtree and the other is not, the path must cross edge z_id if is_x_in_subtree != is_y_in_subtree: is_z_on_path = True # Case 1: Forbidden edge z_id is NOT on the shortest (MST) path if not is_z_on_path: # The MST path is valid and the shortest. Output its length mod MOD. results.append(get_mod_sum(current_path_xor_sum)) # Case 2: Forbidden edge z_id IS on the shortest (MST) path else: # Need to find the shortest alternative path. # Iterate through all non-MST edges to find potential alternative paths. min_alt_path_xor_sum = float('inf') # Use infinity for minimum tracking found_alt = False # Flag if any alternative path is found # Re-identify u_for_z based on depth for subtree check below # This is needed because it was inside the `if z_id in mst_edge_ids` block z_edge_info = edge_map_by_id[z_id] zu, zv = z_edge_info['u'], z_edge_info['v'] u_for_z = -1 if depth[zu] > depth[zv]: u_for_z = zu elif depth[zv] > depth[zu]: u_for_z = zv # If u_for_z remains -1, something is wrong (e.g., endpoints at same depth? Only if root edge?) for k_idx in non_mst_edges_idx: # Check if V_k value exists for this index k_idx if k_idx not in V_k: continue # Get endpoints p, q of the non-MST edge k p, q = edges_info[k_idx]['u'], edges_info[k_idx]['v'] # Check if cycle C_k (formed by edge k and MST path p<->q) contains the forbidden edge z_id # This happens if p and q are separated by edge z_id # i.e., one of p,q is in the subtree of u_for_z (child endpoint of z_id), and the other is not. if u_for_z == -1: continue # Skip if child endpoint identification failed is_p_in_subtree = is_ancestor(u_for_z, p) is_q_in_subtree = is_ancestor(u_for_z, q) # If endpoints p,q are separated by edge z_id if is_p_in_subtree != is_q_in_subtree: # Calculate the XOR sum of the alternative path P' = P_MST XOR C_k alt_path_xor_sum = current_path_xor_sum ^ V_k[k_idx] # Update minimum alternative path length found so far if alt_path_xor_sum < min_alt_path_xor_sum: min_alt_path_xor_sum = alt_path_xor_sum found_alt = True # Mark that at least one alternative path exists # After checking all non-MST edges: if not found_alt: # If no alternative path was found, it means removing z_id disconnects x and y. results.append("-1") else: # Output the length of the shortest alternative path found, modulo MOD. results.append(get_mod_sum(min_alt_path_xor_sum)) # Print all computed results for the queries sys.stdout.write('\n'.join(map(str, results)) + '\n') solve()