#include using namespace std; using ll = long long; template using Pa = pair; template using vec = vector; template using vvec = vector>; class strong_components{ private: vector> v,rv,nv; vector rs,visited,cmp,cmp_size; void dfs(int n){ visited[n] = 1; for(auto x:v[n]) if(!visited[x]) dfs(x); rs.push_back(n); } void rdfs(int n,int cnt){ visited[n] = 1; cmp[n] = cnt; for(auto x:rv[n]) if(!visited[x]) rdfs(x,cnt); } public: strong_components(int N,vector>& graph){ v = graph; rv = vector>(N); visited = cmp = cmp_size = vector(N,0); for(int i=0;i=0;i--) if(!visited[rs[i]]) rdfs(rs[i],now++); nv = vector>(now); for(int i=0;i> v; public: SAT(int N):N(N){ v = vector>(2*N); } void add_closure(int x, int y ,bool bx, bool by){ v[x+(!bx)*N].push_back(y+by*N); v[y+(!by)*N].push_back(x+bx*N); } vector solve(){ strong_components scc(2*N,v); //不可能か判定 vector res(N); for(int i=0;i {}; res[i] = (scc.find(i)> N; vec S(N),T(N),U(N); for(auto& x:S) cin >> x; for(auto& x:T) cin >> x; for(auto& x:U) cin >> x; auto id = [&](int x,int y){ return x*N+y; }; SAT satashun(N*N); for(int i=0;i