#include #include const int Mod = 1000000007; typedef struct List { struct List *next; int v, id; } list; typedef struct { int *par, *size; } UF_forest; void UF_initialize(UF_forest *F, int n) { int i; F->par = (int*)malloc(sizeof(int) * (n + 1)); F->size = (int*)malloc(sizeof(int) * (n + 1)); for (i = 1; i <= n; i++) { F->par[i] = i; F->size[i] = 1; } } int UF_root(UF_forest *F, int v) { if (F->par[v] == v) return v; else { F->par[v] = UF_root(F, F->par[v]); return F->par[v]; } } void UF_merge(UF_forest *F, int u, int v) { u = UF_root(F, u); v = UF_root(F, v); if (u == v) return; else if (F->size[u] > F->size[v]) { F->par[v] = u; F->size[u] += F->size[v]; } else { F->par[u] = v; F->size[v] += F->size[u]; } } int LCA(int par[][200001], int depth[], int u, int w) { int i; while (depth[u] > depth[w]) { for (i = 0; depth[par[i][u]] >= depth[w]; i++); u = par[i-1][u]; } while (depth[u] < depth[w]) { for (i = 0; depth[par[i][w]] >= depth[u]; i++); w = par[i-1][w]; } while (u != w) { for (i = 0; par[i][u] != par[i][w]; i++); if (i > 0) i--; u = par[i][u]; w = par[i][w]; } return u; } int distance(int par[][200001], int dist[][200001], int depth[], int u, int w) { int i; long long ans = 0; while (depth[u] > depth[w]) { for (i = 0; depth[par[i][u]] >= depth[w]; i++); ans += dist[i-1][u]; u = par[i-1][u]; } while (depth[u] < depth[w]) { for (i = 0; depth[par[i][w]] >= depth[u]; i++); ans += dist[i-1][w]; w = par[i-1][w]; } while (u != w) { for (i = 0; par[i][u] != par[i][w]; i++); if (i > 0) i--; ans += dist[i][u] + dist[i][w]; u = par[i][u]; w = par[i][w]; } return (int)(ans % Mod); } int main() { int i, N, M, A[200001], B[200001]; scanf("%d %d", &N, &M); for (i = 0; i < M; i++) scanf("%d %d", &(A[i]), &(B[i])); int pow[200001]; for (i = 1, pow[0] = 2; i < M; i++) pow[i] = pow[i-1] * 2 % Mod; int j, u, w, tree[200001] = {}; list *adj[200001] = {}, e[400001], *p; UF_forest F; UF_initialize(&F, N); for (i = 0, j = 0; i < M; i++) { u = UF_root(&F, A[i]); w = UF_root(&F, B[i]); if (u != w) { UF_merge(&F, u, w); tree[i] = 1; u = A[i]; w = B[i]; e[j].v = w; e[j].id = i; e[j].next = adj[u]; adj[u] = &(e[j++]); e[j].v = u; e[j].id = i; e[j].next = adj[w]; adj[w] = &(e[j++]); } } int x, par[20][200001] = {}, par_edge[200001], dist[20][200001], depth[200001], q[200001], head, tail; par[0][1] = -1; par_edge[1] = -1; depth[1] = 0; depth[0] = -1; q[0] = 1; for (head = 0, tail = 1; head < tail; head++) { u = q[head]; for (p = adj[u]; p != NULL; p = p->next) { w = p->v; if (par[0][w] != 0) continue; par[0][w] = u; par_edge[w] = p->id; dist[0][w] = pow[p->id]; for (i = 0, x = u; par[i][x] > 0; x = par[i++][x]) { par[i+1][w] = par[i][x]; dist[i+1][w] = dist[i][w] + dist[i][x]; if (dist[i+1][w] >= Mod) dist[i+1][w] -= Mod; } depth[w] = depth[u] + 1; q[tail++] = w; } } int alt[200001]; for (i = 0; i < M; i++) alt[i] = -1; for (i = 0; i < M; i++) { if (tree[i] != 0) continue; x = LCA(par, depth, A[i], B[i]); u = A[i]; while (depth[u] > depth[x]) { j = par_edge[u]; if (j < 0) break; w = (depth[A[j]] < depth[B[j]])? A[j]: B[j]; if (depth[w] < depth[x]) break; alt[j] = i; par_edge[u] = par_edge[x]; u = w; } u = B[i]; while (depth[u] > depth[x]) { j = par_edge[u]; if (j < 0) break; w = (depth[A[j]] < depth[B[j]])? A[j]: B[j]; if (depth[w] < depth[x]) break; alt[j] = i; par_edge[u] = par_edge[x]; u = w; } } int Q, y, z, lca[5]; scanf("%d", &Q); for (i = 1; i <= Q; i++) { scanf("%d %d %d", &x, &y, &z); z--; if (tree[z] == 0) { printf("%d\n", distance(par, dist, depth, x, y)); continue; } u = (depth[A[z]] < depth[B[z]])? A[z]: B[z]; w = A[z] + B[z] - u; lca[0] = LCA(par, depth, x, y); lca[1] = LCA(par, depth, x, w); lca[2] = LCA(par, depth, y, u); lca[3] = LCA(par, depth, y, w); lca[4] = LCA(par, depth, x, u); if (depth[u] >= depth[lca[0]] && ((lca[1] == w && lca[2] == lca[0]) || (lca[3] == w && lca[4] == lca[0]))) { if (alt[z] == -1) printf("-1\n"); else { if (LCA(par, depth, LCA(par, depth, x, A[alt[z]]), w) == w || LCA(par, depth, LCA(par, depth, y, B[alt[z]]), w) == w) printf("%lld\n", ((long long)pow[alt[z]] + distance(par, dist, depth, x, A[alt[z]]) + distance(par, dist, depth, y, B[alt[z]])) % Mod); else printf("%lld\n", ((long long)pow[alt[z]] + distance(par, dist, depth, x, B[alt[z]]) + distance(par, dist, depth, y, A[alt[z]])) % Mod); } } else printf("%d\n", distance(par, dist, depth, x, y)); } fflush(stdout); return 0; }