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)] depths = [0] * N cost = [0] * N while stack: u, prev = stack.pop() for v, c in nodes[u]: if v != prev: self.nxt[0][v] = u depths[v] = depths[u] + 1 cost[v] = cost[u] + c stack.append((v, u)) 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<