#include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair P; typedef pair P3; typedef pair

PP; constexpr ll MOD = 998244353; constexpr int IINF = INT_MAX; constexpr ll LLINF = LLONG_MAX; constexpr int MAX_N = int(1e6) + 5; constexpr double EPS = 1e-8; constexpr int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0}; #define REP(i, n) for (int i = 0; i < n; i++) #define REPR(i, n) for (int i = n; i >= 0; i--) #define SORT(v) sort((v).begin(), (v).end()) #define SORTR(v) sort((v).rbegin(), (v).rend()) #define ALL(v) (v).begin(), (v).end() struct SCC { int N; vector > g, gr, g2i, t; vector visited; vector i2g; stack order; SCC(){} SCC(int n){init(n);} void init(int n){ N = n; g.clear(); g.resize(n); gr.clear(); gr.resize(n); visited.resize(n); i2g.resize(n); } void add_edge(int u, int v) { g[u].emplace_back(v); gr[v].emplace_back(u); } void dfs(int x) { if (visited[x]) return; visited[x] = true; for (int i : g[x]) dfs(i); order.push(x); } void rdfs(int x, int k) { if (i2g[x] != -1) return; i2g[x] = k; for (int i : gr[x]) rdfs(i, k); } void build() { fill(visited.begin(), visited.end(), false); fill(i2g.begin(), i2g.end(), -1); for (int i = 0; i < N; i++) dfs(i); int p = 0; while (!order.empty()) { rdfs(order.top(), p++); order.pop(); } g2i.clear(); g2i.resize(p); for(int i=0;i ls; TwoSAT(){} TwoSAT(int n):N(n+1),scc((n+1)*2){} int neg(int a){return (-a+N*2)%(N*2);} void add_edge(int a, int b){ a = (a+N*2)%(N*2); b = (b+N*2)%(N*2); scc.add_edge(a,b); } void add_if(int a, int b){ // a -> b <=> !b -> !a add_edge(a,b); add_edge(neg(b),neg(a)); } void add_iff(int a, int b){ // (a <=> b) <=> a -> b and b -> a } void add_or(int a, int b){ // a or b <=> !a -> b and !b -> a add_if(neg(a),b); } void add_nand(int a, int b){ // a nand b <=> a -> !b and b -> !a add_if(a, neg(b)); } void set_true(int a){ // a <=> !a -> a add_edge(neg(a), a); } void set_false(int a){ // !a <=> a -> !a add_edge(a, neg(a)); } bool build(){ scc.build(); bool ok = true; for(int i=1;i scc.i2g[i+N]){ ls.push_back(i); } else{ ls.push_back(neg(i)); } } } return ok; } }; int main(){ int n, m; cin >> n >> m; TwoSAT twosat(n); vector l(n), r(n); for(int i=0;i> l[i] >> r[i]; } for(int i=0;i