#include #include #include #include #include using namespace std; 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+1); 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; vector U(N); for(int i=0;i> U[i]; if(N>=60){ cout << "Impossible" << endl; return 0; } SAT sat(N); for(int i=0;i s; string s1 = U[i].substr(0,1+k),t1 = U[i].substr(1+k,2-k); string s2 = U[j].substr(0,1+l),t2 = U[j].substr(1+l,2-l); s.insert(s1),s.insert(s2),s.insert(t1),s.insert(t2); if(s.size()!=4) sat.add_closure(i,j,k,l); } } vector res = sat.solve(); if(res.empty()){ cout << "Impossible" << endl; return 0; } for(int i=0;i