#include using namespace std; #include using namespace atcoder; // #include // using namespace boost::multiprecision; #define ll long long #define ld long double #define rep(i, n) for (ll i = 0; i < (ll)(n); ++i) #define vi vector #define vl vector #define vd vector #define vb vector #define vs vector #define vc vector #define ull unsigned long long #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() template inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; } // #define ll int // #define ll int128_t // #define ll int256_t // #define ll cpp_int constexpr ll inf = (1ll << 60); // constexpr ll inf = (1 << 30); // const double PI=3.1415926535897932384626433832795028841971; // ll rui(ll a,ll b){ // if(b==0)return 1; // if(b%2==1) return a*rui(a*a,b/2); // return rui(a*a,b/2); // } // vl fact; // ll kai(ll n){ // fact.resize(n,1); // rep(i,n-1)fact[i+1]=fact[i]*(i+1); // } // using mint = ld; using mint = modint998244353;//static_modint<998244353> // using mint = modint1000000007;//static_modint<1000000007> // using mint = static_modint<922267487>; // 多分落とされにくい NOT ntt-friendly // using mint = static_modint<469762049>; // ntt-friendly // using mint = static_modint<167772161>; // ntt-friendly // using mint = modint;//mint::set_mod(mod); // ll const mod=1000000007ll; // ll const mod=998244353ll; // ll modrui(ll a,ll b,ll mod){ // a%=mod; // if(b==0)return 1; // if(b%2==1) return a*modrui(a*a%mod,b/2,mod)%mod; // return modrui(a*a%mod,b/2,mod)%mod; // } // void incr(vl &v,ll n){// n進法 // ll k=v.size(); // v[k-1]++; // ll now=k-1; // while (v[now]>=n) // { // v[now]=0; // if(now==0)break; // v[now-1]++; // now--; // } // return; // } vector fact,invf; void init_modfact(ll sz){ fact.resize(sz); invf.resize(sz); fact[0]=1; rep(i,sz-1){ fact[i+1]=fact[i]*(i+1); } invf[sz-1]=1/fact[sz-1]; for(ll i=sz-2; i>=0; i--){ invf[i]=invf[i+1]*(i+1); } } mint choose(ll n,ll r){ if(n modpow,invpow; // void init_modpow(ll x,ll sz){ // mint inv=1/mint(x); // modpow.assign(sz,1); // invpow.assign(sz,1); // rep(i,sz-1){ // modpow[i+1]=modpow[i]*x; // invpow[i+1]=invpow[i]*inv; // } // } // long long phi(long long n) {// O(sqrt(n)) // long long res = n; // for (long long i = 2; i * i <= n; i++) { // if (n % i == 0) { // res -= res / i; // while (n % i == 0) n /= i; // } // } // if (n > 1) res -= res / n; // return res; // } string p=""; ll n; vs invmp; void dfs(string const&s,map &mp,vl &to,ll i=0,ll d=0,ll cnt=0){ if(to.size()>=n)return; if(i==n){ if(d!=0)return; if(mp.find(p)==mp.end()){ mp[p]=mp.size(); invmp.push_back(p); } ll id=mp[p]; to.push_back(id); return; } if(s[i]!=')'){ p+='('; cnt++; d++; i++; if(cnt<=n/2)dfs(s,mp,to,i,d,cnt); i--; d--; cnt--; p.pop_back(); } if(to.size()>=n)return; if(s[i]!='('){ p+=')'; d--; i++; if(d>=0)dfs(s,mp,to,i,d,cnt); i--; d++; p.pop_back(); } } void solve(){ cin >> n; vs s(n); rep(i,n)cin >> s[i]; if(n&1){ cout << -1 < mp; vector to(n); rep(i,n){ p=""; dfs(s[i],mp,to[i]); } ll y=mp.size(); mf_graph mf(n+y+2); ll ss=n+y,tt=n+y+1; rep(i,n){ mf.add_edge(ss,i,1); for(auto j:to[i]){ mf.add_edge(i,j+n,1); } } rep(i,y){ mf.add_edge(i+n,tt,1); } ll f=mf.flow(ss,tt); if(f!=n){ cout << -1 << endl; return; } vs ans(n); auto es=mf.edges(); for(auto e:es){ if(e.from> t; while (t--){ solve(); } }