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 e in right[::-1]: res = self.segfunc(res,e) return res class _csr: def __init__(self, n, edges): self.start = [0] * (n + 1) self.elist = [0] * len(edges) for v, _ in edges: self.start[v + 1] += 1 for i in range(1, n + 1): self.start[i] += self.start[i - 1] counter = self.start.copy() for v, e in edges: self.elist[counter[v]] = e counter[v] += 1 class scc_graph: """It calculates the strongly connected components of directed graphs. """ def __init__(self, n): """It creates a directed graph with n vertices and 0 edges. Constraints ----------- > 0 <= n <= 10 ** 8 Complexity ---------- > O(n) """ self.n = n self.edges = [] def add_edge(self, from_, to): """It adds a directed edge from the vertex `from_` to the vertex `to`. Constraints ----------- > 0 <= from_ < n > 0 <= to < n Complexity ---------- > O(1) amortized """ # assert 0 <= from_ < self.n # assert 0 <= to < self.n self.edges.append((from_, to)) def _scc_ids(self): g = _csr(self.n, self.edges) now_ord = 0 group_num = 0 visited = [] low = [0] * self.n order = [-1] * self.n ids = [0] * self.n parent = [-1] * self.n stack = [] for i in range(self.n): if order[i] == -1: stack.append(i) stack.append(i) while stack: v = stack.pop() if order[v] == -1: low[v] = order[v] = now_ord now_ord += 1 visited.append(v) for i in range(g.start[v], g.start[v + 1]): to = g.elist[i] if order[to] == -1: stack.append(to) stack.append(to) parent[to] = v else: low[v] = min(low[v], order[to]) else: if low[v] == order[v]: while True: u = visited.pop() order[u] = self.n ids[u] = group_num if u == v: break group_num += 1 if parent[v] != -1: low[parent[v]] = min(low[parent[v]], low[v]) for i, x in enumerate(ids): ids[i] = group_num - 1 - x return group_num, ids def scc(self): """It returns the list of the "list of the vertices" that satisfies the following. > Each vertex is in exactly one "list of the vertices". > Each "list of the vertices" corresponds to the vertex set of a strongly connected component. The order of the vertices in the list is undefined. > The list of "list of the vertices" are sorted in topological order, i.e., for two vertices u, v in different strongly connected components, if there is a directed path from u to v, the list contains u appears earlier than the list contains v. Complexity ---------- > O(n + m), where m is the number of added edges. """ group_num, ids = self._scc_ids() groups = [[] for _ in range(group_num)] for i, x in enumerate(ids): groups[x].append(i) return groups def popcount(x): '''xの立っているビット数をカウントする関数 (xは64bit整数)''' # 2bitごとの組に分け、立っているビット数を2bitで表現する x = x - ((x >> 1) & 0x5555555555555555) # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333) x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと x = x + (x >> 8) # 16bitごと x = x + (x >> 16) # 32bitごと x = x + (x >> 32) # 64bitごと = 全部の合計 return x & 0x0000007f popcnt = [popcount(i) for i in range(2**20)] def solve(N,A,B,M,E): A = [a-1 for a in A] B = [b-1 for b in B] G = scc_graph(N) edge = [[] for v in range(N)] for u,v in E: edge[u-1].append(v-1) edge[v-1].append(u-1) group = [-1 for v in range(N)] for v in range(N): mex = [False for i in range(len(edge[v])+1)] for nv in edge[v]: if nv < v and group[nv] < len(mex): mex[group[nv]] = True for i in range(len(mex)): if not mex[i]: group[v] = i break n = max(group) + 1 clique = [[] for g in range(n)] for v in range(N): clique[group[v]].append(v) def direct(i,j): if i < j: return A[i] < B[j] else: return B[i] < A[j] def hamilton_path(V): n = len(V) if n <= 1: return V A = hamilton_path(V[:n//2]) B = hamilton_path(V[n//2:]) res = [] bi = 0 for ai in range(len(A)): while bi