import sys def input(): return sys.stdin.readline().strip() def list2d(a, b, c): return [[c] * b for i in range(a)] def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)] def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)] def ceil(x, y=1): return int(-(-x // y)) def INT(): return int(input()) def MAP(): return map(int, input().split()) def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)] def Yes(): print('Yes') def No(): print('No') def YES(): print('YES') def NO(): print('NO') sys.setrecursionlimit(10 ** 9) INF = 10 ** 19 MOD = 10 ** 9 + 7 EPS = 10 ** -10 class LCA: """ LCA(最小共通祖先) """ def __init__(self, nodes, root): self.N = len(nodes) nv = 1 MAX = 0 while nv < self.N: nv *= 2 MAX += 1 self.MAX = MAX self.nxt = list2d(MAX, self.N, -1) self.depths, self.cost = self.dfs(self.N, nodes, root) for k in range(1, MAX): for v in range(self.N): if self.nxt[k-1][v] == -1: continue self.nxt[k][v] = self.nxt[k-1][self.nxt[k-1][v]] def dfs(self, N, nodes, src): stack = [(src, -1, 0, 0)] depths = [INF] * N cost = [INF] * N while stack: u, prev, d, c = stack.pop() depths[u] = d cost[u] = c self.nxt[0][u] = prev for v, nxc in nodes[u]: if v != prev: stack.append((v, u, d+1, c+nxc)) return depths, cost def get_lca(self, a, b): if self.depths[a] > self.depths[b]: a, b = b, a gap = self.depths[b] - self.depths[a] for i in range(self.MAX): if gap & 1<