#include #include using namespace std; using ll = long long; bool check(string candidate, string t) { for (int i = 0; i < candidate.size(); i++) { if (t[i] != '.' && candidate[i] != t[i]) return false; } return true; } 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; int calls = 0; auto f = [&](auto self, int pos, int depth, int opCount) -> void { calls++; 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] && T[i].size() - pos - 1 - (close[T[i].size()] - close[pos + 1]) + opCount + 1 <= N / 2) { buffer[pos] = '('; self(self, pos + 1, depth + 1, opCount + 1); } } if ((T[i][pos] == '.' || T[i][pos] == ')') && depth > 0) { buffer[pos] = ')'; self(self, pos + 1, depth - 1, opCount); } }; f(f, 0, 0, 0); cout << "CALLS=" << calls << endl; 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; } cout << "GRAPH START" << endl; // 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; } }