#include using namespace std; // #include // using namespace atcoder; // #define int long long #define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i) #define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i) #define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--) #define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--) #define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i) #define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i) #define irreps(i, m, n) for (long long i = ((long long)(n)-1); i > (long long)(m); ++i) #define SORT(v, n) sort(v, v + n); #define REVERSE(v, n) reverse(v, v+n); #define vsort(v) sort(v.begin(), v.end()); #define all(v) v.begin(), v.end() #define mp(n, m) make_pair(n, m); #define cinline(n) getline(cin,n); #define replace_all(s, b, a) replace(s.begin(),s.end(), b, a); #define PI (acos(-1)) #define FILL(v, n, x) fill(v, v + n, x); #define sz(x) (long long)(x.size()) using ll = long long; using vi = vector; using vvi = vector; using vll = vector; using vvll = vector; using pii = pair; using pll = pair; using vs = vector; using vpll = vector>; using vtp = vector>; using vb = vector; using ld = long double; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } template using vc=vector; template using vvc=vc>; const ll INF = 1e9+10; const ll MOD = 1e9+7; // const ll MOD = 998244353; const ll LINF = 1e18; struct StronglyConnectedComponents { int n; vector> G, rG; vector order, component; vector used; void dfs(int v) { used[v] = 1; for (auto nv : G[v]) { if (!used[nv]) dfs(nv); } order.push_back(v); } void rdfs(int v, int k) { component[v] = k; for (auto nv : rG[v]) { if (component[nv] < 0) rdfs(nv, k); } } StronglyConnectedComponents(vector> &_G) { n = _G.size(); G = _G; rG.resize(n); component.assign(n, -1); used.resize(n); for (int v = 0; v < n; v++) { for (auto nv : G[v]) rG[nv].push_back(v); } for (int v = 0; v < n; v++) if (!used[v]) dfs(v); int k = 0; reverse(order.begin(), order.end()); for (auto v : order) if (component[v] == -1) rdfs(v, k), k++; } /// 頂点(u, v)が同じ強連結成分に含まれるか bool is_same(int u, int v) { return component[u] == component[v]; } /// 強連結成分を1つのノードに潰したグラフを再構築する vector> rebuild() { int N = *max_element(component.begin(), component.end()) + 1; vector> rebuildedG(N); set> connected; for (int v = 0; v < N; v++) { for (auto nv : G[v]) { if (component[v] != component[nv] and !connected.count(pair(v, nv))) { connected.insert(pair(v, nv)); rebuildedG[component[v]].push_back(component[nv]); } } } return rebuildedG; } }; // implication graph // 1つの区間を1つのノードと捉える // 反転した区間を¬と捉える // ある2つの区間が重なる可能性があるとき、A∨Bとして辺を張る signed main() { cin.tie( 0 ); ios::sync_with_stdio( false ); int n,m; cin>>n>>m; vc l(n), r(n); rep(i,n) cin>>l[i]>>r[i]; vc> G(2*n); rep(i,n){ irep(j,i+1,n){ int l1=l[i], r1=r[i], l2=l[j], r2=r[j]; int L1=m-r1-1, R1=m-l1-1, L2=m-r2-1, R2=m-l2-1; if(l1<=l2 and l2<=r1 or l1<=r2 and r2<=r1 or l2<=l1 and l1<=r2){ // A∨B <=> ¬A=>B∧¬B=>A G[i+n].push_back(j); G[j+n].push_back(i); } if(l1<=L2 and L2<=r1 or l1<=R2 and R2<=r1 or L2<=l1 and l1<=R2){ // A∨¬B <=> ¬A=>¬B∧B=>A G[i+n].push_back(j+n); G[j].push_back(i); } if(L1<=l2 and l2<=R1 or L1<=r2 and r2<=R1 or l2<=L1 and L1<=r2){ // ¬A∨B <=> A=>B∧¬B=>¬A G[i].push_back(j); G[j+n].push_back(i+n); } if(L1<=L2 and L2<=R1 or L1<=R2 and R2<=R1 or L2<=L1 and L1<=R2){ // ¬A∨¬B <=> A=>¬B∧B=>¬A G[i].push_back(j+n); G[j].push_back(i+n); } } } // rep(i,n){ // cout<