#include #include using namespace std; using ll = long long; vector GetN(string pattern, int N) { int n = pattern.size(); vector> dp(n + 1, vector(n + 1, false)); dp[n][0] = true; for (int i = n - 1; i >= 0; i--) { for (int d = 0; d <= n; d++) { if (pattern[i] == '(' || pattern[i] == '.') { if (d + 1 <= n && dp[i + 1][d + 1]) dp[i][d] = true; } if (pattern[i] == ')' || pattern[i] == '.') { if (d - 1 >= 0 && dp[i + 1][d - 1]) dp[i][d] = true; } } } vector res; string buffer = ""; auto dfs = [&](auto self, int pos, int depth) -> void { if (res.size() >= N) return; if (pos == n) { res.push_back(buffer); return; } if ((pattern[pos] == '(' || pattern[pos] == '.') && depth + 1 <= n) { if (dp[pos + 1][depth + 1]) { buffer.push_back('('); self(self, pos + 1, depth + 1); buffer.pop_back(); } } if (res.size() < N && (pattern[pos] == ')' || pattern[pos] == '.') && depth - 1 >= 0) { if (dp[pos + 1][depth - 1]) { buffer.push_back(')'); self(self, pos + 1, depth - 1); buffer.pop_back(); } } }; if (dp[0][0]) { dfs(dfs, 0, 0); } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; assert(1 <= N && N <= 200); vector T(N); for (int i = 0; i < N; i++) { cin >> T[i]; assert(T[i].size() == N); } if (N % 2 == 1) { cout << "-1" << endl; return 0; } map cand2idx; vector idx2cand; vector> candidate; for (int i = 0; i < N; i++) { // vector close(N + 1); // for (int j = 1; j <= N; j++) // { // close[j] = close[j - 1] + (T[i][j] != '('); // } // vector buffer(N); // vector res; // auto f = [&](auto self, int pos, int depth) -> void // { // if (res.size() == N) // return; // if (pos == T[i].size()) // { // res.push_back(string(buffer.begin(), buffer.end())); // return; // } // if (T[i][pos] == '.' || T[i][pos] == '(') // { // if (depth + 1 <= close[T[i].size()] - close[pos + 1]) // { // buffer[pos] = '('; // self(self, pos + 1, depth + 1); // } // } // if ((T[i][pos] == '.' || T[i][pos] == ')') && depth > 0) // { // buffer[pos] = ')'; // self(self, pos + 1, depth - 1); // } // }; // f(f, 0, 0); vector res = GetN(T[i], N); if (res.size() == 0) { cout << "-1" << endl; return 0; } for (int j = 0; j < res.size(); j++) { if (cand2idx.find(res[j]) == cand2idx.end()) { cand2idx[res[j]] = idx2cand.size(); idx2cand.push_back(res[j]); candidate.push_back({ i }); } else { candidate[cand2idx[res[j]]].push_back(i); } } } if (candidate.size() < N) { cout << "-1" << endl; return 0; } // C <= N^2 int C = candidate.size(); int source = 0; int sink = 1; int candHead = 2; int tHead = candHead + C; atcoder::mf_graph g(2 + C + N); for (int i = 0; i < C; i++) { g.add_edge(source, candHead + i, 1); } for (int i = 0; i < N; i++) { g.add_edge(tHead + i, sink, 1); } for (int i = 0; i < C; i++) { for (int j = 0; j < candidate[i].size(); j++) { g.add_edge(candHead + i, tHead + candidate[i][j], 1); } } int maxflow = g.flow(source, sink); if (maxflow != N) { cout << "-1" << endl; return 0; } auto edges = g.edges(); vector S(N); for (int i = 0; i < edges.size(); i++) { if (edges[i].from == source || edges[i].to == sink) continue; if (edges[i].flow == 1) { S[edges[i].to - tHead] = idx2cand[edges[i].from - candHead]; } } for (int i = 0; i < N; i++) { cout << S[i] << endl; } }