#include using namespace std; using Int = long long; //BEGIN CUT HERE struct SCC{ vector > G,R,T,C; vector vs,used,blg; SCC(){} SCC(int n):G(n),R(n),used(n),blg(n){} void add_edge(int u,int v){ G[u].emplace_back(v); R[v].emplace_back(u); } void dfs(int v){ used[v]=1; for(int u:G[v]) if(!used[u]) dfs(u); vs.emplace_back(v); } void rdfs(int v,int k){ used[v]=1; blg[v]=k; C[k].emplace_back(v); for(int u:R[v]) if(!used[u]) rdfs(u,k); } int build(){ int n=G.size(); for(int v=0;v=0;i--){ if(!used[vs[i]]){ T.emplace_back(); C.emplace_back(); rdfs(vs[i],k++); } } for(int v=0;v v <=> !v -> !u scc.add_edge(u,v); scc.add_edge(negate(v),negate(u)); } void add_or(int u,int v){ // u or v <=> !u -> v add_if(negate(u),v); } void add_nand(int u,int v){ // u nand v <=> u -> !v add_if(u,negate(v)); } void set_true(int v){ // v <=> !v -> v scc.add_edge(negate(v),v); } void set_false(int v){ // !v <=> v -> !v scc.add_edge(v,negate(v)); } vector build(){ scc.build(); vector res(n); for(int i=0;iscc[n+i]; } return res; } }; //END CUT HERE signed CFR441_C(){ int n,m; scanf("%d %d",&n,&m); vector> G(n); for(int i=0;i &as,vector &bs){ int x=min(as.size(),bs.size()); int i; for(i=0;ibs.size())) NG(); }; for(int i=0;i+1 ans; for(int i=0;i>n>>m; vector l(n),r(n); for(int i=0;i>l[i]>>r[i],r[i]++; auto check=[&](int al,int ar,int bl,int br){ return max(al,bl)>n; vector u(n); for(int i=0;i>u[i]; auto NO=[](){cout<<"Impossible"<=100) NO(); TwoSat ts(n); for(int i=0;i