#include using namespace std; struct edge{ int to; long long cap; int rev;}; class Dinic{ public: int n; vector> Es; //i番目の辺がどこにあるか. vector> Graph; Dinic():n(0){} Dinic(int N):n(N),Graph(N){} int addedge(int u, int v, long long c){ //u->vに容量c. int m = Es.size(); Es.push_back({u,Graph.at(u).size()}); int gv = Graph.at(v).size(), gu = Graph.at(u).size(); Graph.at(u).push_back(edge{v,c,gv}); Graph.at(v).push_back(edge{u,0,gu}); return m; } long long maxflow(int s, int t,long long limit = numeric_limits::max()){ //s->tにいくつ流せるか. long long ret = 0; vector dist(n),search(n); auto bfs = [&]() -> void { queue Q; fill(dist.begin(),dist.end(),-1); dist.at(s) = 0,Q.push(s); while(Q.size()){ int pos = Q.front(); Q.pop(); for(auto e : Graph.at(pos)){ if(e.cap == 0 || dist.at(e.to) != -1) continue; dist.at(e.to) = dist.at(pos)+1; if(e.to == t) return; Q.push(e.to); } } }; auto dfs = [&](auto dfs,int pos,long long f){ if(pos == s) return f; long long flow = 0; int nowd = dist.at(pos); for(int &i=search.at(pos); i> mincost(int s){ //maxflowの後の復元 vector already(n); queue Q; Q.push(s),already.at(s) = true; while(Q.size()){ int pos = Q.front(); Q.pop(); for(auto e : Graph.at(pos)) if(e.cap && !already.at(e.to)) already.at(e.to) = true,Q.push(e.to); } vector> ret; for(auto [pos,i] : Es) if(already.at(pos)){ edge &e = Graph.at(pos).at(i); if(!already.at(e.to)) ret.push_back({pos,e.to}); } return ret; //[from,to]は辺の追加順になっている. } }; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector S(N),T; vector> To(N); map M; for(auto &s : S) cin >> s; auto solve = [&](int p) -> void { string s = S.at(p); vector> dp(N+1,vector(N+1)); dp.at(N).at(0) = true; for(int i=N-1; i>=0; i--){ char c = s.at(i); if(c != ')') for(int k=0; k void { if(ok == N) return; if(v < 0 || dp.at(pos).at(v) == false) return; if(pos == N){ if(!M.count(now)) M[now] = T.size(),T.emplace_back(now); To.at(p).push_back(M[now]),ok++; return; } if(s.at(pos) != ')'){ now.at(pos) = '('; dfs(dfs,pos+1,v+1); } if(s.at(pos) != '('){ now.at(pos) = ')'; dfs(dfs,pos+1,v-1); } }; dfs(dfs,0,0); }; for(int i=0; i answer(N); for(int i=0; i