############################################################################################ import bisect,collections,copy,heapq,itertools,math,string,sys,queue,time,random from decimal import Decimal from typing import List, Optional, Tuple import sys def I() -> str: """ 標準入力から1行読み取る（改行なし） Returns: 入力された文字列 """ return input() def IS(): """ 標準入力から1行読み取り、空白で分割する Returns: 分割された文字列のリスト """ return input().split() def II() -> int: """ 標準入力から整数を1つ読み取る Returns: 入力された整数 """ return int(input()) def IIS(): """ 標準入力から1行読み取り、空白で分割して整数のリストにする Returns: 整数のリスト 使い方: a, b = IIS() # 2つの整数を受け取る arr = IIS() # 任意個の整数をリストで受け取る """ return list(map(int, input().split())) def LIIS(): """ IIS() のエイリアス 標準入力から1行読み取り、空白で分割して整数のリストにする Returns: 整数のリスト """ return list(map(int, input().split())) """ べき乗の高速計算・逆元の計算 機能: - 繰り返し二乗法による高速なべき乗計算 O(log N) - 逆元の計算（フェルマーの小定理） O(log mod) - 逆元の計算（拡張ユークリッドの互除法） O(log min(a, mod)) - 組み合わせ計算（mod込み） 使い方: # べき乗 pow_mod(2, 10, 1000000007) # 2^10 mod 10^9+7 # 逆元 inv = mod_inverse(3, 1000000007) # 3の逆元 mod 10^9+7 # 組み合わせ comb = Combination(10**6, 10**9+7) print(comb.nCr(10, 3)) # 10C3 """ from typing import Tuple def pow_mod(a: int, n: int, mod: int) -> int: """a^n mod mod を高速に計算する（繰り返し二乗法） Args: a: 底 n: 指数 mod: 法 Returns: a^n mod mod 計算量: O(log N) """ result = 1 a %= mod while n > 0: if n & 1: result = (result * a) % mod a = (a * a) % mod n >>= 1 return result def mod_inverse_fermat(a: int, mod: int) -> int: """フェルマーの小定理による逆元の計算 mod が素数の場合に使用可能 a^(-1) ≡ a^(mod-2) (mod mod) Args: a: 逆元を求める数 mod: 法（素数） Returns: a の逆元 mod mod 計算量: O(log mod) """ return pow_mod(a, mod - 2, mod) def extgcd(a: int, b: int) -> Tuple[int, int, int]: """拡張ユークリッドの互除法 ax + by = gcd(a, b) を満たす x, y を求める Args: a, b: 整数 Returns: (gcd(a, b), x, y) 計算量: O(log min(a, b)) """ if b == 0: return a, 1, 0 g, x, y = extgcd(b, a % b) return g, y, x - (a // b) * y def mod_inverse_extgcd(a: int, mod: int) -> int: """拡張ユークリッドの互除法による逆元の計算 mod が素数でなくても使用可能（gcd(a, mod) = 1 が必要） Args: a: 逆元を求める数 mod: 法 Returns: a の逆元 mod mod（存在しない場合は -1） 計算量: O(log min(a, mod)) """ g, x, _ = extgcd(a, mod) if g != 1: return -1 # 逆元が存在しない return x % mod class Combination: """組み合わせ計算（mod 込み） 階乗と逆元を前計算して高速に nCr を計算する """ def __init__(self, n: int, mod: int): """ Args: n: 計算する組み合わせの最大値 mod: 法（素数） 計算量: O(N) """ self.n = n self.mod = mod # 階乗を前計算 self.fact = [1] * (n + 1) for i in range(1, n + 1): self.fact[i] = (self.fact[i - 1] * i) % mod # 逆元を前計算 self.inv_fact = [1] * (n + 1) self.inv_fact[n] = mod_inverse_fermat(self.fact[n], mod) for i in range(n - 1, -1, -1): self.inv_fact[i] = (self.inv_fact[i + 1] * (i + 1)) % mod def nCr(self, n: int, r: int) -> int: """nCr mod mod を計算する Args: n, r: 組み合わせのパラメータ Returns: nCr mod mod 計算量: O(1) """ if n < 0 or r < 0 or n < r: return 0 return (self.fact[n] * self.inv_fact[r] % self.mod * self.inv_fact[n - r] % self.mod) def nPr(self, n: int, r: int) -> int: """nPr mod mod を計算する（順列） Args: n, r: 順列のパラメータ Returns: nPr mod mod 計算量: O(1) """ if n < 0 or r < 0 or n < r: return 0 return (self.fact[n] * self.inv_fact[n - r] % self.mod) def nHr(self, n: int, r: int) -> int: """重複組み合わせ nHr = (n+r-1)Cr Args: n, r: パラメータ Returns: nHr mod mod 計算量: O(1) """ return self.nCr(n + r - 1, r) # def make_divisors(n: int) -> list[int]: # """整数 n の約数をすべて列挙する # Args: # n: 約数を列挙する整数（n >= 1） # Returns: # n の約数のリスト（昇順） # 計算量: O(√N) # """ # lower_divisors = [] # upper_divisors = [] # i = 1 # while i * i <= n: # if n % i == 0: # lower_divisors.append(i) # if i != n // i: # upper_divisors.append(n // i) # i += 1 # return lower_divisors + upper_divisors[::-1] # sys.setrecursionlimit(10**7) alpha="ABCDEFGHIJKLMNOPQRSTUVWXYZ" def bit_count(x): return bin(x).count("1") def yesno(f): if f:print("Yes") else:print("No") MOD=998244353 from functools import lru_cache INF=10**18 # import pypyjit # pypyjit.set_param("trace_limit=24000,vec=1") # pypyjit.set_param('max_unroll_recursion=-1') from collections import deque from typing import List, Tuple import heapq class MaxFlow: """最大流アルゴリズム（Dinic法）""" def __init__(self, n: int): """ Args: n: 頂点数 """ self.n = n self.graph = [[] for _ in range(n)] def add_edge(self, u: int, v: int, cap: int): """辺を追加する（u → v に容量capの辺）""" self.graph[u].append([v, cap, len(self.graph[v])]) self.graph[v].append([u, 0, len(self.graph[u]) - 1]) def bfs(self, s: int, t: int) -> bool: """BFSでレベルグラフを構築する""" self.level = [-1] * self.n self.level[s] = 0 queue = deque([s]) while queue: v = queue.popleft() for to, cap, _ in self.graph[v]: if cap > 0 and self.level[to] < 0: self.level[to] = self.level[v] + 1 queue.append(to) return self.level[t] >= 0 def dfs(self, v: int, t: int, f: int) -> int: """DFSで増加パスを見つけて流す""" if v == t: return f for i in range(self.iter[v], len(self.graph[v])): self.iter[v] = i to, cap, rev = self.graph[v][i] if cap > 0 and self.level[v] < self.level[to]: d = self.dfs(to, t, min(f, cap)) if d > 0: self.graph[v][i][1] -= d self.graph[to][rev][1] += d return d return 0 def max_flow(self, s: int, t: int) -> int: """最大流を求める Args: s: 始点 t: 終点 Returns: 最大流量 """ flow = 0 while self.bfs(s, t): self.iter = [0] * self.n while True: f = self.dfs(s, t, float('inf')) if f == 0: break flow += f return flow def min_cut(self, s: int) -> List[int]: """最小カットに含まれる頂点のリストを返す（始点側） max_flow実行後に呼び出す。 """ visited = [False] * self.n queue = deque([s]) visited[s] = True while queue: v = queue.popleft() for to, cap, _ in self.graph[v]: if cap > 0 and not visited[to]: visited[to] = True queue.append(to) return [i for i in range(self.n) if visited[i]] class MinCostFlow: """最小費用流アルゴリズム（ダイクストラ法 + ポテンシャル）""" def __init__(self, n: int): """ Args: n: 頂点数 """ self.n = n self.graph = [[] for _ in range(n)] def add_edge(self, u: int, v: int, cap: int, cost: int): """辺を追加する（u → v に容量cap、コストcostの辺）""" self.graph[u].append([v, cap, cost, len(self.graph[v])]) self.graph[v].append([u, 0, -cost, len(self.graph[u]) - 1]) def min_cost_flow(self, s: int, t: int, max_flow: int) -> Tuple[int, int]: """最小費用流を求める Args: s: 始点 t: 終点 max_flow: 流す流量の上限 Returns: (流量, 最小費用) のタプル """ res = 0 flow = 0 h = [0] * self.n while flow < max_flow: # ダイクストラ法で最短路を探す dist = [float('inf')] * self.n dist[s] = 0 prev_v = [-1] * self.n prev_e = [-1] * self.n pq = [(0, s)] while pq: d, v = heapq.heappop(pq) if dist[v] < d: continue for i, (to, cap, cost, _) in enumerate(self.graph[v]): if cap > 0 and dist[to] > dist[v] + cost + h[v] - h[to]: dist[to] = dist[v] + cost + h[v] - h[to] prev_v[to] = v prev_e[to] = i heapq.heappush(pq, (dist[to], to)) if dist[t] == float('inf'): break # ポテンシャルを更新 for v in range(self.n): if dist[v] < float('inf'): h[v] += dist[v] # 流せる量を計算 d = max_flow - flow v = t while v != s: d = min(d, self.graph[prev_v[v]][prev_e[v]][1]) v = prev_v[v] # 流す flow += d res += d * h[t] v = t while v != s: e = prev_e[v] self.graph[prev_v[v]][e][1] -= d rev = self.graph[prev_v[v]][e][3] self.graph[v][rev][1] += d v = prev_v[v] return flow, res class BipartiteMatching: """二部グラフの最大マッチング（タイムスタンプ最適化版）""" def __init__(self, n: int, m: int): """ Args: n: 左側の頂点数 m: 右側の頂点数 """ self.n = n self.m = m self.graph = [[] for _ in range(n)] self.match_right = [-1] * m self.match_left = [-1] * n self.used = [] self.timestamp = 0 def add_edge(self, u: int, v: int): """辺を追加する（左側のu → 右側のv）""" self.graph[u].append(v) def dfs(self, v: int) -> bool: """増加パスを探す""" for to in self.graph[v]: if self.used[to] == self.timestamp: continue self.used[to] = self.timestamp if self.match_right[to] == -1 or self.dfs(self.match_right[to]): self.match_right[to] = v self.match_left[v] = to return True return False def max_matching(self) -> int: """最大マッチング数を返す""" self.used = [0] * self.m res = 0 for v in range(self.n): self.timestamp += 1 if self.dfs(v): res += 1 return res def get_matching(self) -> List[Tuple[int, int]]: """マッチングの辺のリストを返す（max_matching実行後に呼び出す）""" edges = [] for v in range(self.m): if self.match_right[v] != -1: edges.append((self.match_right[v], v)) return edges class MinVertexCover: """二部グラフの最小点被覆（ケーニッヒの定理）""" def __init__(self, n: int, m: int): """ Args: n: 左側の頂点数 m: 右側の頂点数 """ self.n = n self.m = m self.matching = BipartiteMatching(n, m) def add_edge(self, u: int, v: int): """辺を追加する（左側のu → 右側のv）""" self.matching.add_edge(u, v) def min_vertex_cover(self) -> Tuple[int, List[int], List[int]]: """最小点被覆を求める Returns: (最小点被覆数, 左側の頂点リスト, 右側の頂点リスト) """ max_match = self.matching.max_matching() visited_left = [False] * self.n visited_right = [False] * self.m # マッチングされていない左側の頂点からDFS def dfs(v: int): if visited_left[v]: return visited_left[v] = True for to in self.matching.graph[v]: if not visited_right[to]: visited_right[to] = True if self.matching.match_right[to] != -1: dfs(self.matching.match_right[to]) for v in range(self.n): if self.matching.match_left[v] == -1: dfs(v) # 最小点被覆: 訪問されなかった左側 + 訪問された右側 left_cover = [v for v in range(self.n) if not visited_left[v]] right_cover = [v for v in range(self.m) if visited_right[v]] return max_match, left_cover, right_cover class MaxIndependentSet: """二部グラフの最大独立集合""" def __init__(self, n: int, m: int): """ Args: n: 左側の頂点数 m: 右側の頂点数 """ self.n = n self.m = m self.min_cover = MinVertexCover(n, m) def add_edge(self, u: int, v: int): """辺を追加する（左側のu → 右側のv）""" self.min_cover.add_edge(u, v) def max_independent_set(self) -> Tuple[int, List[int], List[int]]: """最大独立集合を求める Returns: (最大独立集合数, 左側の頂点リスト, 右側の頂点リスト) """ cover_size, left_cover, right_cover = self.min_cover.min_vertex_cover() left_cover_set = set(left_cover) right_cover_set = set(right_cover) left_independent = [v for v in range(self.n) if v not in left_cover_set] right_independent = [v for v in range(self.m) if v not in right_cover_set] independent_size = self.n + self.m - cover_size return independent_size, left_independent, right_independent class MinEdgeCover: """二部グラフの最小辺被覆""" def __init__(self, n: int, m: int): """ Args: n: 左側の頂点数 m: 右側の頂点数 """ self.n = n self.m = m self.matching = BipartiteMatching(n, m) self.graph = [[] for _ in range(n)] def add_edge(self, u: int, v: int): """辺を追加する（左側のu → 右側のv）""" self.matching.add_edge(u, v) self.graph[u].append(v) def min_edge_cover(self) -> Tuple[int, List[Tuple[int, int]]]: """最小辺被覆を求める Returns: (最小辺被覆数, 辺のリスト) """ max_match = self.matching.max_matching() matching_edges = self.matching.get_matching() matched_left = set() matched_right = set() for u, v in matching_edges: matched_left.add(u) matched_right.add(v) edges = list(matching_edges) # 左側の未マッチ頂点に辺を追加 for u in range(self.n): if u not in matched_left and self.graph[u]: edges.append((u, self.graph[u][0])) # 右側の未マッチ頂点に辺を追加 for u in range(self.n): for v in self.graph[u]: if v not in matched_right: edges.append((u, v)) matched_right.add(v) break return len(edges), edges #################################################### class PrefixSum1D: """1次元累積和（動的拡張・遅延評価対応版） 更新時に累積和を即座に再計算せず、クエリ時に必要な範囲のみを遅延計算します。 これにより、複数回更新してから少数のクエリを行う場合に効率的です。 Args: arr: 数値のリスト（省略可能） mod: オプション。指定した場合、すべての計算でこの値によるモジュロ演算が適用されます Usage: ps = PrefixSum1D(arr) # arr: 1次元リスト ps = PrefixSum1D(arr, mod=10**9+7) # モジュロ演算付き ps.query(l, r) # [l, r) の合計 (0-indexed, 半開区間) """ __slots__ = ('n', 'arr', 'S', 'dirty_from', 'mod') def __init__(self, arr=None, mod=None): """ Args: arr: 数値のリスト（省略可能） mod: オプション。モジュロ演算の値 """ if arr is None: arr = [] n = len(arr) self.n = n self.mod = mod # 元の配列を保持（値の取得と更新に使用） self.arr = list(arr) # S[i] = arr[0] + arr[1] + ... + arr[i-1]（1-indexed） self.S = [0] * (n + 1) if mod is not None: for i in range(n): self.S[i + 1] = (self.S[i] + arr[i]) % mod else: for i in range(n): self.S[i + 1] = self.S[i] + arr[i] # 累積和が無効になっている範囲の最小インデックス（-1なら全て有効） self.dirty_from = -1 def _rebuild_from(self, start_idx, end_idx=None): """ start_idx以降の累積和を再計算（内部用） Args: start_idx: 再計算を開始するインデックス（0-indexed） end_idx: 再計算を終了するインデックス（0-indexed、この位置は含まない） Noneの場合は最後まで再計算 """ if start_idx < 0 or start_idx >= self.n: return if end_idx is None: end_idx = self.n else: end_idx = min(end_idx, self.n) S = self.S arr = self.arr mod = self.mod if mod is not None: for i in range(start_idx, end_idx): S[i + 1] = (S[i] + arr[i]) % mod else: for i in range(start_idx, end_idx): S[i + 1] = S[i] + arr[i] # dirty範囲を更新 if end_idx >= self.n: self.dirty_from = -1 else: self.dirty_from = end_idx def _ensure_valid(self, up_to_idx): """ up_to_idxまでの累積和が有効であることを保証（内部用） Args: up_to_idx: 保証する範囲の終端インデックス（1-indexed） """ if self.dirty_from != -1 and self.dirty_from < up_to_idx: self._rebuild_from(self.dirty_from, up_to_idx) def query(self, l, r): """arr[l] + arr[l+1] + ... + arr[r-1] を返す（0-indexed, 半開区間 [l, r)） 必要に応じて累積和を遅延計算します。 単一要素クエリ (長さ1) の場合は配列から直接返します。 """ # 単一要素クエリの高速パス if r - l == 1: return self.arr[l] # _ensure_validをインライン化 df = self.dirty_from if df != -1 and df < r: self._rebuild_from(df, r) result = self.S[r] - self.S[l] if self.mod is not None: result %= self.mod return result def query_clamped(self, l, r): """arr[l] + arr[l+1] + ... + arr[r-1] を返す（0-indexed, 半開区間 [l, r)） 範囲外の指定を自動的に有効範囲に狭めます。 Args: l: 左端インデックス（負の値や範囲外も可） r: 右端インデックス（範囲外も可） Returns: 指定範囲（クランプ後）の合計 Examples: >>> ps = PrefixSum1D([1, 2, 3, 4, 5]) >>> ps.query_clamped(-10, 3) # 範囲: [0, 3) 6 >>> ps.query_clamped(2, 100) # 範囲: [2, 5) 12 >>> ps.query_clamped(-5, 100) # 範囲: [0, 5) 15 """ # 範囲を [0, n] にクランプ n = self.n if l < 0: l = 0 elif l > n: l = n if r < 0: r = 0 elif r > n: r = n # l > r の場合は 0 を返す if l >= r: return 0 # 単一要素クエリの高速パス if r - l == 1: return self.arr[l] # _ensure_validをインライン化 df = self.dirty_from if df != -1 and df < r: self._rebuild_from(df, r) result = self.S[r] - self.S[l] if self.mod is not None: result %= self.mod return result def total(self): """全要素の合計を返す 必要に応じて累積和を遅延計算します。 """ self._ensure_valid(self.n) return self.S[self.n] def get(self, i): """ i番目の要素を取得（O(1)） Args: i: インデックス（0-indexed） Returns: arr[i]の値 """ if not 0 <= i < self.n: raise IndexError(f"index {i} out of range [0, {self.n})") return self.arr[i] def __getitem__(self, i): """arr[i]を返す（Pythonの配列風アクセス）""" return self.get(i) def update(self, i, value): """ i番目の要素を更新（O(1) 遅延評価） 累積和の再計算を遅延させるため、この操作は即座に完了します。 実際の累積和はクエリ時に必要な範囲のみ計算されます。 Args: i: インデックス（0-indexed） value: 新しい値 """ if not 0 <= i < self.n: raise IndexError(f"index {i} out of range [0, {self.n})") # mod適用 if self.mod is not None: value %= self.mod # 元の配列を更新 self.arr[i] = value # dirty範囲を更新（まだdirtyでないか、より前のインデックスの場合） if self.dirty_from == -1 or i < self.dirty_from: self.dirty_from = i def append(self, value): """ 配列の末尾に要素を追加（O(1)） Args: value: 追加する値 """ # mod適用 if self.mod is not None: value %= self.mod # 元の配列に追加 self.arr.append(value) # 累積和が有効な場合のみ追加 if self.dirty_from == -1: if self.mod is not None: self.S.append((self.S[self.n] + value) % self.mod) else: self.S.append(self.S[self.n] + value) else: # dirtyな場合は累積和配列だけ拡張（値は後で計算） self.S.append(0) self.n += 1 def append_multiple(self, arr): """ 複数の要素を一度に追加（O(len(arr))） Args: arr: 追加する値のリスト """ for value in arr: self.append(value) def pop(self): """ 配列の末尾から要素を削除して返す（O(1)） Returns: 削除した値 Raises: IndexError: 配列が空の場合 """ if self.n == 0: raise IndexError("pop from empty array") # 削除する値を取得 value = self.arr[self.n - 1] self.arr.pop() self.S.pop() self.n -= 1 # dirty範囲が削除された要素を含む場合は調整 if self.dirty_from != -1 and self.dirty_from >= self.n: self.dirty_from = -1 if self.n == 0 else self.n - 1 return value def __len__(self): """配列の長さを返す""" return self.n def __repr__(self): """デバッグ用の文字列表現""" return f"PrefixSum1D({self.arr})" n=II() T=[I() for i in range(n)] li=[[] for i in range(n)] # li2=[[] for i in range(n)] right=[] s=[] cnt2=0 for i in range(n): cnt2=0 p=[0]*n for j in range(n): if T[i][j]!="(": p[j]+=1 p=PrefixSum1D(p) def f(num,cnt): global cnt2 if cnt2>=n:return if num==n: if cnt==0: cnt2+=1 li[i].append("".join(s)) right.append("".join(s)) return if T[i][num]!=")" and cnt+1<=p.query(num+1,n): s.append("(") f(num+1,cnt+1) s.pop() if cnt>0 and T[i][num]!="(": s.append(")") f(num+1,cnt-1) s.pop() f(0,0) right = list(set(right)) dic = collections.defaultdict(int) for i in range(len(right)): dic[right[i]]=i bm=BipartiteMatching(n,len(right)) for i in range(n): for j in li[i]: bm.add_edge(i,dic[j]) if bm.max_matching()!=n: print(-1) exit() li2=bm.get_matching() li2.sort() for i,j in li2: print(right[j]) print(0)