#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include typedef long long ll; using namespace std; #define debug(x) cerr << #x << " = " << (x) << endl; #define mod 1000000007 //1e9+7(prime number) #define INF 1000000000 //1e9 #define LLINF 2000000000000000000LL //2e18 #define SIZE 2010 struct SCC{ int n; vector > G, rG; vector vs; vector used; vector cmp; //属する強連結成分番号(トポロジカル順) SCC(int _n):n(_n),G(_n),rG(_n),cmp(_n){} void add_edge(int from, int to){ G[from].push_back(to); rG[to].push_back(from); } void dfs(int v){ used[v] = true; for(int i=0;i=0;i--) if(!used[vs[i]]) rdfs(vs[i], k++); return k; //強連結成分数 } }; struct TwoSAT{ int n; SCC scc; vector ans; TwoSAT(int _n):n(_n), scc(_n*2), ans(_n){} //1-index, add(1, -2) -> p or not q void add(int a, int b){ a = a > 0 ? a - 1 : n - a - 1; b = b > 0 ? b - 1 : n - b - 1; scc.add_edge((a + n)%(2*n), b); scc.add_edge((b + n)%(2*n), a); } bool solve(){ scc.solve(); for(int i=0;i scc.cmp[n+i]; return true; } }; /* A => B ... not A or B */ int main(){ int n,m; int l[SIZE], r[SIZE], rl[SIZE], rr[SIZE]; scanf("%d%d",&n,&m); for(int i=0;i