using System; using System.Collections.Generic; using System.Linq; class TwoSAT { int N = 0; int nextId = 0; Vertex[] vertices = { }; bool[] visits = { }; // 連結リストと逆向きの連結リスト List[] list = null; List[] rlist = null; class Vertex { public Vertex(int num, int id) { Number = num; ID = id; } public int Number = 0; public int ID = 0; } public TwoSAT(int n) { N = n; // 連結リストを生成する list = new List[n * 2]; rlist = new List[n * 2]; for (int i = 0; i < n * 2; i++) { list[i] = new List(); rlist[i] = new List(); } } public void AddConstraintV(bool xTrue, int x, bool yTrue, int y) { if (!xTrue) x = TakeNot(x); if (!yTrue) y = TakeNot(y); list[TakeNot(x)].Add(y); list[TakeNot(y)].Add(x); rlist[y].Add(TakeNot(x)); rlist[x].Add(TakeNot(y)); } public void AddConstraintArrow(bool xTrue, int x, bool yTrue, int y) { if (!xTrue) x = TakeNot(x); if (!yTrue) y = TakeNot(y); list[x].Add(y); list[y].Add(x); rlist[y].Add(x); rlist[x].Add(y); } int TakeNot(int x) { if (x < N) return x + N; else return x - N; } public List Solve() { visits = new bool[N * 2]; vertices = new Vertex[N * 2]; for (int i = 0; i < N * 2; i++) Dfs1(i, list); vertices = vertices.OrderByDescending(_ => _.ID).ToArray(); int groupNumber = 0; Dictionary dic = new Dictionary(); visits = new bool[N * 2]; foreach (Vertex vertex in vertices) { List ret = Dfs2(vertex.Number, rlist); foreach (int i in ret) dic.Add(i, groupNumber); groupNumber++; } List values = new List(); for (int i = 0; i < N; i++) { if (dic[i] == dic[TakeNot(i)]) return new List(); if (dic[i] > dic[TakeNot(i)]) values.Add(true); else values.Add(false); } return values; } void Dfs1(int vNum, List[] list) { if (!visits[vNum]) { visits[vNum] = true; dfs(vNum); } void dfs(int num) { foreach (int i in list[num]) { if (visits[i]) continue; visits[i] = true; dfs(i); } vertices[num] = new Vertex(num, nextId++); } } List Dfs2(int vNum, List[] list) { List rets = new List(); // たどり着ける頂点をリストにして返す if (!visits[vNum]) // 一度訪問した頂点は対象外 { rets.Add(vNum); visits[vNum] = true; dfs(vNum); } return rets; void dfs(int num) { foreach (int i in list[num]) { if (visits[i]) continue; visits[i] = true; dfs(i); rets.Add(i); } } } } public class Program { static void Main() { int N, M; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; M = vs[1]; } int[] L = new int[N]; int[] R = new int[N]; for (int i = 0; i < N; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); L[i] = vs[0]; R[i] = vs[1]; } TwoSAT twoSAT = new TwoSAT(N); for (int a = 0; a < N; a++) { for (int b = a + 1; b < N; b++) { bool b1 = (R[b] < L[a] || R[a] < L[b]); bool b2 = (M - L[b]- 1 < L[a] || R[a] < M - R[b]-1); if (b1 && !b2) // 片方だけ反転すると干渉する { twoSAT.AddConstraintArrow(false, a, false, b); twoSAT.AddConstraintArrow(true, a, true, b); //twoSAT.AddConstraintV(true, a, false, b); //twoSAT.AddConstraintV(false, a, true, b); } if (!b1 && b2) // 片方だけ反転させないと干渉する { twoSAT.AddConstraintArrow(false, a, true, b); twoSAT.AddConstraintArrow(true, a, false, b); //twoSAT.AddConstraintV(true, a, true, b); //twoSAT.AddConstraintV(false, a, false, b); } if (!b1 && !b2) // どうやっても駄目 { Console.WriteLine("NO"); return; } } } List rets = twoSAT.Solve(); if (rets.Count == 0) Console.WriteLine("NO"); else Console.WriteLine("YES"); } }