def divisors(M): d=[] i=1 while M>=i**2: if M%i==0: d.append(i) if i**2!=M: d.append(M//i) i=i+1 return d def popcount(x): x = x - ((x >> 1) & 0x55555555) x = (x & 0x33333333) + ((x >> 2) & 0x33333333) x = (x + (x >> 4)) & 0x0f0f0f0f x = x + (x >> 8) x = x + (x >> 16) return x & 0x0000007f def eratosthenes(n): res=[0 for i in range(n+1)] prime=set([]) for i in range(2,n+1): if not res[i]: prime.add(i) for j in range(1,n//i+1): res[i*j]=1 return prime def factorization(n): res=[] for p in prime: if n%p==0: while n%p==0: n//=p res.append(p) if n!=1: res.append(n) return res def euler_phi(n): res = n for x in range(2,n+1): if x ** 2 > n: break if n%x==0: res = res//x * (x-1) while n%x==0: n //= x if n!=1: res = res//n * (n-1) return res def ind(b,n): res=0 while n%b==0: res+=1 n//=b return res def isPrimeMR(n): if n==1: return 0 d = n - 1 d = d // (d & -d) L = [2, 3, 5, 7, 11, 13, 17] for a in L: t = d y = pow(a, t, n) if y == 1: continue while y != n - 1: y = (y * y) % n if y == 1 or t == n - 1: return 0 t <<= 1 return 1 def findFactorRho(n): from math import gcd m = 1 << n.bit_length() // 8 for c in range(1, 99): f = lambda x: (x * x + c) % n y, r, q, g = 2, 1, 1, 1 while g == 1: x = y for i in range(r): y = f(y) k = 0 while k < r and g == 1: ys = y for i in range(min(m, r - k)): y = f(y) q = q * abs(x - y) % n g = gcd(q, n) k += m r <<= 1 if g == n: g = 1 while g == 1: ys = f(ys) g = gcd(abs(x - ys), n) if g < n: if isPrimeMR(g): return g elif isPrimeMR(n // g): return n // g return findFactorRho(g) def primeFactor(n): i = 2 ret = {} rhoFlg = 0 while i*i <= n: k = 0 while n % i == 0: n //= i k += 1 if k: ret[i] = k i += 1 + i % 2 if i == 101 and n >= 2 ** 20: while n > 1: if isPrimeMR(n): ret[n], n = 1, 1 else: rhoFlg = 1 j = findFactorRho(n) k = 0 while n % j == 0: n //= j k += 1 ret[j] = k if n > 1: ret[n] = 1 if rhoFlg: ret = {x: ret[x] for x in sorted(ret)} return ret def divisors(n): res = [1] prime = primeFactor(n) for p in prime: newres = [] for d in res: for j in range(prime[p]+1): newres.append(d*p**j) res = newres res.sort() return res def xorfactorial(num):#排他的論理和の階乗 if num==0: return 0 elif num==1: return 1 elif num==2: return 3 elif num==3: return 0 else: x=baseorder(num) return (2**x)*((num-2**x+1)%2)+function(num-2**x) def xorconv(n,X,Y): if n==0: res=[(X[0]*Y[0])%mod] return res x=[digit[i]+X[i+2**(n-1)] for i in range(2**(n-1))] y=[Y[i]+Y[i+2**(n-1)] for i in range(2**(n-1))] z=[digit[i]-X[i+2**(n-1)] for i in range(2**(n-1))] w=[Y[i]-Y[i+2**(n-1)] for i in range(2**(n-1))] res1=xorconv(n-1,x,y) res2=xorconv(n-1,z,w) former=[(res1[i]+res2[i])*inv for i in range(2**(n-1))] latter=[(res1[i]-res2[i])*inv for i in range(2**(n-1))] former=list(map(lambda x:x%mod,former)) latter=list(map(lambda x:x%mod,latter)) return former+latter def merge_sort(A,B): pos_A,pos_B = 0,0 n,m = len(A),len(B) res = [] while pos_A < n and pos_B < m: a,b = A[pos_A],B[pos_B] if a < b: res.append(a) pos_A += 1 else: res.append(b) pos_B += 1 res += A[pos_A:] res += B[pos_B:] return res class UnionFindVerSize(): def __init__(self, N): self._parent = [n for n in range(0, N)] self._size = [1] * N self.group = N def find_root(self, x): if self._parent[x] == x: return x self._parent[x] = self.find_root(self._parent[x]) stack = [x] while self._parent[stack[-1]]!=stack[-1]: stack.append(self._parent[stack[-1]]) for v in stack: self._parent[v] = stack[-1] return self._parent[x] def unite(self, x, y): gx = self.find_root(x) gy = self.find_root(y) if gx == gy: return self.group -= 1 if self._size[gx] < self._size[gy]: self._parent[gx] = gy self._size[gy] += self._size[gx] else: self._parent[gy] = gx self._size[gx] += self._size[gy] def get_size(self, x): return self._size[self.find_root(x)] def is_same_group(self, x, y): return self.find_root(x) == self.find_root(y) class SegmentTree: def __init__(self, init_val, segfunc, ide_ele): n = len(init_val) self.segfunc = segfunc self.ide_ele = ide_ele self.num = 1 << (n - 1).bit_length() self.tree = [ide_ele] * 2 * self.num self.size = n for i in range(n): self.tree[self.num + i] = init_val[i] for i in range(self.num - 1, 0, -1): self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1]) def update(self, k, x): k += self.num self.tree[k] = x while k > 1: k >>= 1 self.tree[k] = self.segfunc(self.tree[2*k],self.tree[2*k+1]) def query(self, l, r): if r==self.size: r = self.num res = self.ide_ele l += self.num r += self.num right = [] while l < r: if l & 1: res = self.segfunc(res, self.tree[l]) l += 1 if r & 1: right.append(self.tree[r-1]) l >>= 1 r >>= 1 for y in right[::-1]: res = self.segfunc(res,y) return res class DualSegmentTree: def __init__(self, n, segfunc, ide_ele): self.segfunc = segfunc self.ide_ele = ide_ele self.num = 1 << (n - 1).bit_length() self.tree = [ide_ele] * 2 * self.num def update(self,l,r,x): l += self.num r += self.num while l < r: if l & 1: self.tree[l] = self.segfunc(self.tree[l],x) l += 1 if r & 1: self.tree[r-1] = self.segfunc(self.tree[r-1],x) l >>= 1 r >>= 1 def __getitem__(self,idx): idx += self.num res = self.ide_ele while idx: res = self.segfunc(res,self.tree[idx]) idx>>=1 return res import sys,random,bisect from collections import deque,defaultdict from heapq import heapify,heappop,heappush from itertools import permutations from math import gcd,log input = lambda :sys.stdin.buffer.readline() mi = lambda :map(int,input().split()) li = lambda :list(mi()) mod = 10**9 + 7 solver = random.randint(0,99)%2 solver = 0 if solver==0: N,M = mi() uf = UnionFindVerSize(N) E = [] edge = [[] for v in range(N)] gomi = [] cost = 2 for i in range(M): u,v = mi() u,v = u-1,v-1 E.append((u,v,i,cost)) if not uf.is_same_group(u,v): uf.unite(u,v) edge[u].append((v,i,cost)) edge[v].append((u,i,cost)) else: gomi.append((u,v,i,cost)) cost = 2 * cost % mod root = random.randint(0,N-1) root = 2 parent = [root for v in range(N)] depth = [0 for v in range(N)] rank = [0 for v in range(N)] v_to_e = [-1 for i in range(N)] deq = deque([root]) while deq: v = deq.popleft() for nv,idx,c in edge[v]: if nv==parent[v]: continue parent[nv] = v depth[nv] = (depth[v] + c) % mod rank[nv] = rank[v] + 1 v_to_e[nv] = idx deq.append(nv) begin = [0 for v in range(N)] end = [0 for v in range(N)] cnt = [0 for v in range(N)] stack = [root] euler_tour = [] while stack: v = stack[-1] euler_tour.append(v) if cnt[v] == len(edge[v]): end[v] = len(euler_tour) - 1 stack.pop() else: nv,idx,c = edge[v][cnt[v]] cnt[v] += 1 if nv==parent[v]: continue begin[nv] = len(euler_tour) stack.append(nv) init = [(rank[v]<<20)+v for v in euler_tour] seg_lca = SegmentTree(init,min,10**17) mask = 2**20-1 def lca(u,v): l = min(begin[u],begin[v]) r = max(end[u],end[v]) r = seg_lca.query(l,r+1) p = r & mask return p def dist(x,y): p = lca(x,y) return (depth[x] + depth[y] - 2 * depth[p]) % mod Q = int(input()) LCA = [-1 for v in range(Q)] query = [] for _ in range(Q): x,y,z = mi() LCA[_] = lca(x-1,y-1) query.append((x-1,y-1,z-1)) check_time = [[] for v in range(N)] for i in range(Q): x,y,z = query[i] p = LCA[i] check_time[x].append((i,p,z)) check_time[y].append((i,p,z)) alt = [[] for v in range(N)] for u,v,idx,c in gomi[::-1]: p = lca(u,v) while alt[u]: pre_idx,pre_p = alt[u][-1] if rank[pre_p] >= rank[p]: alt[u].pop() else: break alt[u].append((idx,p)) while alt[v]: pre_idx,pre_p = alt[v][-1] if rank[pre_p] >= rank[p]: alt[v].pop() else: break alt[v].append((idx,p)) delete_query = [[] for v in range(N)] for v in range(N): for idx,p in alt[v]: delete_query[p].append(v) z_on_path = [-1 for i in range(Q)] alt_edge = [-1 for v in range(M)] seg = SegmentTree([M]*len(euler_tour),min,M) edge_on_path = [] appear = [-1 for i in range(M)] idx_on_alt = [len(alt[v])-1 for v in range(N)] for i in range(1,len(euler_tour)): v = euler_tour[i] if i==end[v]: if v!=root: appear[edge_on_path.pop()] = -1 for cv in delete_query[v]: idx_on_alt[cv] -= 1 k = idx_on_alt[cv] if k!=-1: seg.update(begin[cv],alt[cv][k][0]) else: seg.update(begin[cv],M) e = v_to_e[v] res = seg.query(begin[v],end[v]) if res!=M: alt_edge[e] = res elif i==begin[v]: idx = v_to_e[v] appear[idx] = len(edge_on_path) edge_on_path.append(idx) for i,p,z in check_time[v]: if rank[p] <= appear[z]: z_on_path[i] = v if alt[v]: seg.update(begin[v],alt[v][-1][0]) for i in range(Q): x,y,z = query[i] p = LCA[i] if z_on_path[i]!=-1: if alt_edge[z]==-1: print(-1) else: u,v,idx,cost = E[alt_edge[z]] pu,pv,_,_ = E[z] if rank[pu] > rank[pv]: pu,pv = pv,pu if z_on_path[i]==y: x,y = y,x if begin[pv] <= begin[u] <= end[pv]: res = dist(u,x) + dist(v,y) + cost else: res = dist(v,x) + dist(u,y) + cost res %= mod print(res) else: res = (depth[x] + depth[y] - 2 * depth[p]) % mod print(res) else: N,M = mi() uf = UnionFindVerSize(N) E = [] edge = [[] for v in range(N)] gomi = [] cost = 2 for i in range(M): u,v = mi() u,v = u-1,v-1 E.append((u,v,i,cost)) if not uf.is_same_group(u,v): uf.unite(u,v) edge[u].append((v,i,cost)) edge[v].append((u,i,cost)) else: gomi.append((u,v,i,cost)) cost = 2 * cost % mod parent = [0 for v in range(N)] depth = [0 for v in range(N)] rank = [0 for v in range(N)] v_to_e = [-1 for i in range(N)] deq = deque([0]) while deq: v = deq.popleft() for nv,idx,c in edge[v]: if nv==parent[v]: continue parent[nv] = v depth[nv] = (depth[v] + c) % mod rank[nv] = rank[v] + 1 v_to_e[nv] = idx deq.append(nv) begin = [0 for v in range(N)] end = [0 for v in range(N)] cnt = [0 for v in range(N)] stack = [0] euler_tour = [0] next = 1 while stack: v = stack[-1] if cnt[v] == len(edge[v]): end[v] = next next += 1 #print(v) euler_tour.append(v) stack.pop() else: nv,idx,c = edge[v][cnt[v]] cnt[v] += 1 if nv==parent[v]: continue begin[nv] = next next += 1 euler_tour.append(nv) stack.append(nv) LV = (N-1).bit_length() def construct(prv): kprv = [prv] S = prv for k in range(LV): T = [0]*N for i in range(N): if S[i] is None: continue T[i] = S[S[i]] kprv.append(T) S = T return kprv kprv=construct(parent) def lca(u, v): dd = rank[v] - rank[u] if dd < 0: u, v = v, u dd = -dd # assert depth[u] <= depth[v] for k in range(LV+1): if dd & 1: v = kprv[k][v] dd >>= 1 # assert depth[u] == depth[v] if u == v: return u for k in range(LV-1, -1, -1): pu = kprv[k][u]; pv = kprv[k][v] if pu != pv: u = pu; v = pv # assert kprv[0][u] == kprv[0][v] return kprv[0][u] def dist(x,y): p = lca(x,y) return (depth[x] + depth[y] - 2 * depth[p]) % mod Q = int(input()) LCA = [-1 for v in range(Q)] query = [] for _ in range(Q): x,y,z = mi() LCA[_] = lca(x-1,y-1) query.append((x-1,y-1,z-1)) check_time = [[] for v in range(N)] for i in range(Q): x,y,z = query[i] p = LCA[i] check_time[x].append((i,p,z)) check_time[y].append((i,p,z)) alt = [[] for v in range(N)] for u,v,idx,c in gomi[::-1]: p = lca(u,v) while alt[u]: pre_idx,pre_p = alt[u][-1] if rank[pre_p] >= rank[p]: alt[u].pop() else: break alt[u].append((idx,p)) while alt[v]: pre_idx,pre_p = alt[v][-1] if rank[pre_p] >= rank[p]: alt[v].pop() else: break alt[v].append((idx,p)) delete_query = [[] for v in range(N)] for v in range(N): for idx,p in alt[v]: delete_query[p].append(v) z_on_path = [-1 for i in range(Q)] alt_edge = [-1 for v in range(M)] seg = SegmentTree([M]*(2*N),min,M) edge_on_path = [] appear = [-1 for i in range(M)] for i in range(1,2*N): v = euler_tour[i] if i==end[v]: if v!=0: appear[edge_on_path.pop()] = -1 for cv in delete_query[v]: alt[cv].pop() if alt[cv]: seg.update(begin[cv],alt[cv][-1][0]) else: seg.update(begin[cv],M) e = v_to_e[v] res = seg.query(begin[v],end[v]) if res!=M: alt_edge[e] = res else: idx = v_to_e[v] appear[idx] = len(edge_on_path) edge_on_path.append(idx) for i,p,z in check_time[v]: if rank[p] <= appear[z]: z_on_path[i] = v if alt[v]: seg.update(begin[v],alt[v][-1][0]) for i in range(Q): x,y,z = query[i] p = LCA[i] if z_on_path[i]!=-1: if alt_edge[z]==-1: print(-1) else: u,v,idx,cost = E[alt_edge[z]] pu,pv,_,_ = E[z] if rank[pu] > rank[pv]: pu,pv = pv,pu if z_on_path[i]==y: x,y = y,x if begin[pv] <= begin[u] <= end[pv]: res = dist(u,x) + dist(v,y) + cost else: res = dist(v,x) + dist(u,y) + cost res %= mod print(res) else: res = (depth[x] + depth[y] - 2 * depth[p]) % mod print(res)