#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include typedef long long ll; using namespace std; #ifndef LOCAL #define debug(x) ; #else #define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl; template ostream &operator<<(ostream &out, const pair &p) { out << "{" << p.first << ", " << p.second << "}"; return out; } template ostream &operator<<(ostream &out, const vector &v) { out << '{'; for (const T &item : v) out << item << ", "; out << "\b\b}"; return out; } #endif #define mod 1000000007 //1e9+7(prime number) #define INF 1000000000 //1e9 #define LLINF 2000000000000000000LL //2e18 #define SIZE 200010 // int main(){ // // // return 0; // } /* Strongly Connected Component */ /* 1. dfsをして、戻るときに1から順に番号を付ける 2. 数値が大きいノードから逆辺を使ってdfsをする。 すでに訪れているノードには行かない。 たどり着けるノードが同じ連結成分に属する。 */ struct SCC{ int n; vector > G, rG; vector vs, cmp; vector used; 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; //強連結成分数 } //属する強連結成分番号(トポロジカル順) int operator[](int k) const { return cmp[k]; } }; /* 2-SAT (Source: 蟻本)*/ 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; } }; int main(){ int n, m; int l[SIZE], r[SIZE], rl[SIZE], rr[SIZE]; scanf("%d%d", &n, &m); for (int i=0; i