############################################################################################ 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 #################################################### n=II() T=[I() for i in range(n)] li=[set() for i in range(n)] # li2=[[] for i in range(n)] right=[] s=[] for i in range(n): cnt2=0 def f(num,cnt): global cnt2 if cnt2>=n:return if num==n: if cnt==0: cnt2+=1 right.append("".join(s)) return if cnt<=n//2 and T[i][num]!=")": 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): cnt=0 for j in range(len(right)): if cnt>=n:break f=1 for k in range(n): if T[i][k]!="." and T[i][k]!=right[j][k]: f=0 break if f: bm.add_edge(i,j) cnt+=1 if bm.max_matching()!=n: print(-1) exit() li2=bm.get_matching() li2.sort() for i,j in li2: print(right[j])