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 WeightedUnionFind(): def __init__(self,N): self.parent = [i for i in range(N)] self.size = [1 for i in range(N)] self.val = [0 for i in range(N)] self.flag = True self.edge = [[] for i in range(N)] def dfs(self,v,pv): stack = [(v,pv)] new_parent = self.parent[pv] while stack: v,pv = stack.pop() self.parent[v] = new_parent for nv,w in self.edge[v]: if nv!=pv: self.val[nv] = self.val[v] + w stack.append((nv,v)) def unite(self,x,y,w): if not self.flag: return if self.parent[x]==self.parent[y]: self.flag = (self.val[x] - self.val[y] == w) return if self.size[self.parent[x]]>self.size[self.parent[y]]: self.edge[x].append((y,-w)) self.edge[y].append((x,w)) self.size[x] += self.size[y] self.val[y] = self.val[x] - w self.dfs(y,x) else: self.edge[x].append((y,-w)) self.edge[y].append((x,w)) self.size[y] += self.size[x] self.val[x] = self.val[y] + w self.dfs(x,y) class Dijkstra(): class Edge(): def __init__(self, _to, _cost): self.to = _to self.cost = _cost def __init__(self, V): self.G = [[] for i in range(V)] self._E = 0 self._V = V @property def E(self): return self._E @property def V(self): return self._V def add_edge(self, _from, _to, _cost): self.G[_from].append(self.Edge(_to, _cost)) self._E += 1 def shortest_path(self, s): import heapq que = [] d = [10**15] * self.V d[s] = 0 heapq.heappush(que, (0, s)) while len(que) != 0: cost, v = heapq.heappop(que) if d[v] < cost: continue for i in range(len(self.G[v])): e = self.G[v][i] if d[e.to] > d[v] + e.cost: d[e.to] = d[v] + e.cost heapq.heappush(que, (d[e.to], e.to)) return d #Z[i]:length of the longest list starting from S[i] which is also a prefix of S #O(|S|) def Z_algorithm(s): N = len(s) Z_alg = [0]*N Z_alg[0] = N i = 1 j = 0 while i < N: while i+j < N and s[j] == s[i+j]: j += 1 Z_alg[i] = j if j == 0: i += 1 continue k = 1 while i+k < N and k + Z_alg[k] 0: res_sum += self.BIT[idx] if mod: res_sum %= mod idx -= idx&(-idx) return res_sum #Ai += x O(logN) def update(self,idx,x): mod = self.mod while idx <= self.num: self.BIT[idx] += x if mod: self.BIT[idx] %= mod idx += idx&(-idx) return class dancinglink(): def __init__(self,n,debug=False): self.n = n self.debug = debug self._left = [i-1 for i in range(n)] self._right = [i+1 for i in range(n)] self.exist = [True for i in range(n)] def pop(self,k): if self.debug: assert self.exist[k] L = self._left[k] R = self._right[k] if L!=-1: if R!=self.n: self._right[L],self._left[R] = R,L else: self._right[L] = self.n elif R!=self.n: self._left[R] = -1 self.exist[k] = False def left(self,idx,k=1): if self.debug: assert self.exist[idx] res = idx while k: res = self._left[res] if res==-1: break k -= 1 return res def right(self,idx,k=1): if self.debug: assert self.exist[idx] res = idx while k: res = self._right[res] if res==self.n: break k -= 1 return res class SparseTable(): def __init__(self,A,merge_func,ide_ele): N=len(A) n=N.bit_length() self.table=[[ide_ele for i in range(n)] for i in range(N)] self.merge_func=merge_func for i in range(N): self.table[i][0]=A[i] for j in range(1,n): for i in range(0,N-2**j+1): f=self.table[i][j-1] s=self.table[i+2**(j-1)][j-1] self.table[i][j]=self.merge_func(f,s) def query(self,s,t): b=t-s+1 m=b.bit_length()-1 return self.merge_func(self.table[s][m],self.table[t-2**m+1][m]) class BinaryTrie: class node: def __init__(self,val): self.left = None self.right = None self.max = val def __init__(self): self.root = self.node(-10**15) def append(self,key,val): pos = self.root for i in range(29,-1,-1): pos.max = max(pos.max,val) if key>>i & 1: if pos.right is None: pos.right = self.node(val) pos = pos.right else: pos = pos.right else: if pos.left is None: pos.left = self.node(val) pos = pos.left else: pos = pos.left pos.max = max(pos.max,val) def search(self,M,xor): res = -10**15 pos = self.root for i in range(29,-1,-1): if pos is None: break if M>>i & 1: if xor>>i & 1: if pos.right: res = max(res,pos.right.max) pos = pos.left else: if pos.left: res = max(res,pos.left.max) pos = pos.right else: if xor>>i & 1: pos = pos.right else: pos = pos.left if pos: res = max(res,pos.max) return res def solveequation(edge,ans,n,m): #edge=[[to,dire,id]...] x=[0]*m used=[False]*n for v in range(n): if used[v]: continue y = dfs(v) if y!=0: return False return x def dfs(v): used[v]=True r=ans[v] for to,dire,id in edge[v]: if used[to]: continue y=dfs(to) if dire==-1: x[id]=y else: x[id]=-y r+=y return r class Matrix(): mod=10 def set_mod(m): Matrix.mod=m def __init__(self,L): self.row=len(L) self.column=len(L[0]) self._matrix=L self._matridigit = [[L[i][j] for j in range(self.column)] for i in range(self.row)] for i in range(self.row): for j in range(self.column): self._matridigit[i][j]%=Matrix.mod def __getitem__(self,item): if type(item)==int: raise IndexError("you must specific row and column") elif len(item)!=2: raise IndexError("you must specific row and column") i,j=item return self._matridigit[i][j] def __setitem__(self,item,val): if type(item)==int: raise IndexError("you must specific row and column") elif len(item)!=2: raise IndexError("you must specific row and column") i,j=item self._matridigit[i][j]=val def __add__(self,other): if (self.row,self.column)!=(other.row,other.column): raise SizeError("sizes of matrixes are different") res=[[0 for j in range(self.column)] for i in range(self.row)] for i in range(self.row): for j in range(self.column): res[i][j]=self._matridigit[i][j]+other._matridigit[i][j] res[i][j]%=Matrix.mod return Matrix(res) def __sub__(self,other): if (self.row,self.column)!=(other.row,other.column): raise SizeError("sizes of matrixes are different") res=[[0 for j in range(self.column)] for i in range(self.row)] for i in range(self.row): for j in range(self.column): res[i][j]=self._matridigit[i][j]-other._matridigit[i][j] res[i][j]%=Matrix.mod return Matrix(res) def __mul__(self,other): if type(other)!=int: if self.column!=other.row: raise SizeError("sizes of matrixes are different") res=[[0 for j in range(other.column)] for i in range(self.row)] for i in range(self.row): for j in range(other.column): temp=0 for k in range(self.column): temp+=self._matridigit[i][k]*other._matrix[k][j] res[i][j]=temp%Matrix.mod return Matrix(res) else: n=other res=[[(n*self._matridigit[i][j])%Matrix.mod for j in range(self.column)] for i in range(self.row)] return Matrix(res) def __pow__(self,m): if self.column!=self.row: raise MatrixPowError("the size of row must be the same as that of column") n=self.row res=Matrix([[int(i==j) for i in range(n)] for j in range(n)]) while m: if m%2==1: res=res*self self=self*self m//=2 return res def __str__(self): res=[] for i in range(self.row): for j in range(self.column): res.append(str(self._matridigit[i][j])) res.append(" ") res.append("\n") res=res[:len(res)-1] return "".join(res) from collections import deque class Dinic: def __init__(self, N): self.N = N self.G = [[] for i in range(N)] def add_edge(self, fr, to, cap): forward = [to, cap, None] forward[2] = backward = [fr, 0, forward] self.G[fr].append(forward) self.G[to].append(backward) def add_multi_edge(self, v1, v2, cap1, cap2): edge1 = [v2, cap1, None] edge1[2] = edge2 = [v1, cap2, edge1] self.G[v1].append(edge1) self.G[v2].append(edge2) def bfs(self, s, t): self.level = level = [None]*self.N deq = deque([s]) level[s] = 0 G = self.G while deq: v = deq.popleft() lv = level[v] + 1 for w, cap, _ in G[v]: if cap and level[w] is None: level[w] = lv deq.append(w) return level[t] is not None def dfs(self, v, t, f): if v == t: return f level = self.level for e in self.it[v]: w, cap, rev = e if cap and level[v] < level[w]: d = self.dfs(w, t, min(f, cap)) if d: e[1] -= d rev[1] += d return d return 0 def flow(self, s, t): flow = 0 INF = 10**9 + 7 G = self.G while self.bfs(s, t): *self.it, = map(iter, self.G) f = INF while f: f = self.dfs(s, t, INF) flow += f return flow 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.readline().rstrip() mi = lambda :map(int,input().split()) li = lambda :list(mi()) mod = 10**9 + 7 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 print(gomi) 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]) topo = [] while deq: v = deq.popleft() topo.append(v) 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) 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 query = [] Q = int(input()) for _ in range(Q): x,y,z = mi() 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(x,y) check_time[x].append((i,p,z)) check_time[y].append((i,p,z)) #print(check_time) z_on_path = [-1 for i in range(Q)] cnt = [0 for v in range(N)] stack = [0] edge_on_path = [] appear = [-1 for i in range(M)] while stack: v = stack[-1] if cnt[v]==len(edge[v]): stack.pop() if v!=0: appear[edge_on_path.pop()] = -1 else: nv,idx,c = edge[v][cnt[v]] cnt[v] += 1 if nv==parent[v]: continue stack.append(nv) appear[idx] = len(edge_on_path) edge_on_path.append(idx) for i,p,z in check_time[nv]: if appear[z]==-1: continue #print(edge_on_path) #print(nv,i,p,z,rank[p],appear[z]) if rank[p] <= appear[z]: z_on_path[i] = nv #print(z_on_path) out_time = [-1 for v in range(M)] alt = [[] for v in range(N)] for u,v,idx,c in gomi: p = lca(u,v) out_time[idx] = p heappush(alt[u],idx) heappush(alt[v],idx) alt_edge = [-1 for v in range(M)] for v in topo[::-1]: for nv,idx,c in edge[v]: if nv==parent[v]: continue if len(alt[nv]) < len(alt[v]): alt[nv],alt[v] = alt[v],alt[nv] for val in alt[nv]: heappush(alt[v],val) alt[nv] = [] while alt[v]: idx = alt[v][0] p = out_time[idx] if rank[v] <= rank[p]: heappop(alt[v]) else: break if alt[v]: e = v_to_e[v] alt_edge[e] = alt[v][0] for i in range(Q): x,y,z = query[i] p = lca(x,y) if z_on_path[i]!=-1: if alt_edge[z]==-1: print(-1) else: u,v,idx,cost = E[alt_edge[z]] if z_on_path[i]==y: x,y = y,x check = lca(x,u) if check==x or lca(check,p)!=p: res = dist(u,x) + dist(v,y) + cost else: res = dist(v,x) + dist(u,y) + cost res %= mod print(res) else: res = dist(x,y) print(res)