// ReSharper disable ArrangeTypeMemberModifiers // ReSharper disable ConvertIfStatementToSwitchStatement // ReSharper disable FunctionRecursiveOnAllPaths // ReSharper disable InconsistentNaming // ReSharper disable InlineOutVariableDeclaration // ReSharper disable InvertIf // ReSharper disable JoinDeclarationAndInitializer // ReSharper disable MemberCanBeMadeStatic.Global // ReSharper disable MemberCanBeMadeStatic.Local // ReSharper disable NonReadonlyMemberInGetHashCode // ReSharper disable PossibleNullReferenceException // ReSharper disable RedundantUsingDirective // ReSharper disable SuggestVarOrType_BuiltInTypes // ReSharper disable SuggestVarOrType_Elsewhere // ReSharper disable TailRecursiveCall // ReSharper disable UnusedMember.Global // ReSharper disable UnusedMember.Local // ReSharper disable UseObjectOrCollectionInitializert #if true && UTAKA_LOCAL //#if false #define UTAKA_DEBUG #endif //#define TOPCODER using System; using System.Collections; using System.Collections.Generic; using System.Collections.Specialized; using System.Diagnostics; using System.IO; using System.Linq; using System.Runtime.CompilerServices; using System.Text; using System.Numerics; using System.Runtime.InteropServices; using System.Security.Cryptography; using static UtakaApp.Util; namespace UtakaApp { public partial class Program { /* https://yukicoder.me/problems/no/274 */ public const string SiteName = "YukiCoder"; public const string ContestName = "274"; public const string ProblemName = ""; public void Solve() { int N = cin.ReadInt; int M = cin.ReadInt; int[] L = new int[N]; int[] R = new int[N]; for (int i = 0; i < N; i++) { L[i] = cin.ReadInt; R[i] = cin.ReadInt; } var g = new DirectedGraph(N * 2); for (int i = 0; i < N; i++) { for (int j = 0; j < i; j++) { int a = L[i]; int b = R[i]; int c = L[j]; int d = R[j]; for (int x = 0; x < 2; x++) { for (int y = 0; y < 2; y++) { if (CommonPoint1D(a, b, c, d)) { g.AddEdge(x * N + i, (1 - y) * N + j); g.AddEdge(y * N + j, (1 - x) * N + i); } a = M - 1 - a; b = M - 1 - b; Swap(ref a, ref b); } c = M - 1 - c; d = M - 1 - d; Swap(ref c, ref d); } } } int countOfScc; int[] scc = g.StronglyConnectedComponents(out countOfScc); int num = g.N / 2; bool impossible = false; for (int i = 0; i < num; i++) { if (scc[i] == scc[N + i]) { impossible = true; break; } } cou.WriteLine(impossible ? "NO" : "YES"); } public bool CommonPoint1D(int a, int b, int c, int d) { return c <= b && a <= d; } public void Swap(ref T a, ref T b) { T c = a; a = b; b = c; } } public class DirectedGraph { public int N; // ノードの数 public List[] Adj; // AddEdgeでu,vを加えたときu->v方向で保存した向き先 public List[] Rev; // AddEdgeでu,vを加えたときv->u方向で保存した向き先 入次数がわかる public bool HasMultipleTopologicalResults; // トポロジカルソートの結果が複数ありえるか private List topologicalResult; // トポロジカルソートした結果の順番  private Stack stack; // 強連結成分を求めるとき使うstack private int[] scc; // 強連結成分 private bool[] usedInDfs; // 強連結成分を求める順方向のdfsですでに使った頂点の記録 private bool[] usedInRDfs; // 強連結成分を求める逆方向のdfsですでに使った頂点の記録 public DirectedGraph(int nodeCount) { N = nodeCount; Adj = new List[N]; Rev = new List[N]; for (int i = 0; i < N; i++) { Adj[i] = new List(); Rev[i] = new List(); } } public void AddEdge(int u, int v) { Adj[u].Add(v); Rev[v].Add(u); } public bool IsDAG() { topologicalResult = topologicalResult ?? TopologicalSort(); return topologicalResult.Count == N; } public List TopologicalSort() { HasMultipleTopologicalResults = false; topologicalResult = new List(N); var counts = new int[N]; // 処理済みの入次数 var st = new Stack(); // 入次数が0の頂点をstackに追加 for (int i = 0; i < N; i++) { if (Rev[i].Count == 0) { st.Push(i); } } while (st.Count > 0) { // stackに1個より多くの要素があるなら、トポロジカルソートの結果は複数存在する HasMultipleTopologicalResults |= st.Count > 1; var curr = st.Pop(); topologicalResult.Add(curr); foreach (int i in Adj[curr]) { counts[i]++; // 入次数分の処理が終わったら、stackに加える if (counts[i] == Rev[i].Count) st.Push(i); } } return topologicalResult; } /// /// 強連結成分分解を実行する /// /// 強連結成分の個数 /// 属する強連結成分のトポロジカル順序 public int[] StronglyConnectedComponents(out int countOfScc) { usedInDfs = new bool[N]; stack = new Stack(); for (var i = 0; i < N; i++) { if (!usedInDfs[i]) { SCCDfs(i); } } scc = new int[N]; for (int i = 0; i < N; i++) { scc[i] = -1; } usedInRDfs = new bool[N]; countOfScc = 0; while (stack.Count > 0) { SCCRDfs(stack.Pop(), countOfScc++); while (stack.Count > 0 && scc[stack.Peek()] != -1) { stack.Pop(); } } return scc; } /// /// 強連結成分を求める順方向のDfs /// private void SCCDfs(int index) { usedInDfs[index] = true; foreach (var ad in Adj[index]) { if (!usedInDfs[ad]) { SCCDfs(ad); } } stack.Push(index); } /// /// 強連結成分を求める逆方向のDfs /// private void SCCRDfs(int index, int topologicalOrderOfScc) { scc[index] = topologicalOrderOfScc; foreach (var ad in Rev[index]) { if (scc[ad] == -1) { SCCRDfs(ad, topologicalOrderOfScc); } } } } //========================================================================================= // Debug IO //========================================================================================= public partial class Program { //========================================================================================= // Main //========================================================================================= private readonly ConsoleInput cin; private readonly IConsole cou; public Program(ConsoleInput cin, IConsole cou) { this.cin = cin; this.cou = cou; } #if !TOPCODER public static void Main(string[] args) { #if UTAKA_LOCAL //#if false new TestCaseCheckerForAtCoder().TestProblems(); #else var cin = new ConsoleInput(System.Console.In); var console = new MyConsole(); new Program(cin, console).Solve(); console.Flush(); #endif } #endif public void WriteEnumerable(IEnumerable A, string delimiter = " ") { var sb = new StringBuilder(); foreach (T v in A) { sb.Append(v); sb.Append(delimiter); } if (sb.Length > 0) { sb.Length--; } cou.WriteLine(sb.ToString()); } } public static class Util { //========================================================================================= // Library //========================================================================================= public static T[] Array1D(int a, T defaultValue) where T : struct { var ret = new T[a]; for (int i = 0; i < a; i++) { ret[i] = defaultValue; } return ret; } public static T[] Array1D(int a) where T : struct { var ret = new T[a]; return ret; } /// /// 要素数 (a, b) の、defaultValue で満たされた配列を作成します。 /// /// 配列の型 /// 1次元の要素数 /// 2次元の要素数 /// デフォルト値 /// 指定した条件で初期化された配列 public static T[,] Array2D(int a, int b, T defaultValue) where T : struct { var ret = new T[a, b]; for (int i = 0; i < a; i++) { for (int j = 0; j < b; j++) { ret[i, j] = defaultValue; } } return ret; } public static T[,,] Array3D(int a, int b, int c, T defaultValue) where T : struct { T[,,] ret = new T[a, b, c]; for (int i = 0; i < a; i++) { for (int j = 0; j < b; j++) { for (int k = 0; k < c; k++) { ret[i, j, k] = defaultValue; } } } return ret; } /// /// 要素数 (a, b) の、defaultValue で満たされたJag配列を作成します。 /// /// 配列の型 /// 1次元の要素数 /// 2次元の要素数 /// デフォルト値 /// 指定した条件で初期化された配列 public static T[][] JagArray2D(int a, int b, T defaultValue) where T : struct { var ret = new T[a][]; for (int i = 0; i < a; i++) { var row = new T[b]; ret[i] = row; for (int j = 0; j < b; j++) { row[j] = defaultValue; } } return ret; } /// /// 要素数 (a, b) のdefault値で満たされたJag配列を作成します。 /// /// 配列の型 /// 1次元の要素数 /// 2次元の要素数 /// 初期化された配列 public static T[][] JagArray2D(int a, int b) where T : struct { var ret = new T[a][]; for (int i = 0; i < a; i++) { ret[i] = new T[b]; } return ret; } public static T[][][] JagArray3D(int a, int b, int c, T defaultValue) where T : struct { var ret = new T[a][][]; for (int i = 0; i < a; i++) { T[][] aRow = new T[b][]; ret[i] = aRow; for (int j = 0; j < b; j++) { T[] bRow = new T[c]; aRow[j] = bRow; for (int k = 0; k < c; k++) { bRow[k] = defaultValue; } } } return ret; } public static T[][][] JagArray3D(int a, int b, int c) where T : struct { var ret = new T[a][][]; for (int i = 0; i < a; i++) { T[][] aRow = new T[b][]; ret[i] = aRow; for (int j = 0; j < b; j++) { T[] bRow = new T[c]; aRow[j] = bRow; } } return ret; } public static T[][][][] JagArray4D(int a, int b, int c, int d, T defaultValue) where T : struct { var ret = new T[a][][][]; for (int i = 0; i < a; i++) { T[][][] aRow = new T[b][][]; ret[i] = aRow; for (int j = 0; j < b; j++) { T[][] bRow = new T[c][]; aRow[j] = bRow; for (int k = 0; k < c; k++) { T[] cRow = new T[d]; bRow[k] = cRow; for (int l = 0; l < d; l++) { cRow[l] = defaultValue; } } } } return ret; } public static T[][][][] JagArray4D(int a, int b, int c, int d) where T : struct { var ret = new T[a][][][]; for (int i = 0; i < a; i++) { T[][][] aRow = new T[b][][]; ret[i] = aRow; for (int j = 0; j < b; j++) { T[][] bRow = new T[c][]; aRow[j] = bRow; for (int k = 0; k < c; k++) { T[] cRow = new T[d]; bRow[k] = cRow; } } } return ret; } public static T[][][][][] JagArray5D(int a, int b, int c, int d, int e, T defaultValue) where T : struct { var ret = new T[a][][][][]; for (int i = 0; i < a; i++) { T[][][][] aRow = new T[b][][][]; ret[i] = aRow; for (int j = 0; j < b; j++) { T[][][] bRow = new T[c][][]; aRow[j] = bRow; for (int k = 0; k < c; k++) { T[][] cRow = new T[d][]; bRow[k] = cRow; for (int l = 0; l < d; l++) { T[] dRow = new T[e]; cRow[l] = dRow; for (int m = 0; m < e; m++) { dRow[m] = defaultValue; } } } } } return ret; } public static T[][][][][] JagArray5D(int a, int b, int c, int d, int e) where T : struct { var ret = new T[a][][][][]; for (int i = 0; i < a; i++) { T[][][][] aRow = new T[b][][][]; ret[i] = aRow; for (int j = 0; j < b; j++) { T[][][] bRow = new T[c][][]; aRow[j] = bRow; for (int k = 0; k < c; k++) { T[][] cRow = new T[d][]; bRow[k] = cRow; for (int l = 0; l < d; l++) { T[] dRow = new T[e]; cRow[l] = dRow; } } } } return ret; } /// /// ジャグ配列をコピーして返す。 /// public static T[][] CopyJagArray2D(T[][] source) where T : struct { int len = source.Length; T[][] dest = new T[len][]; for (int i = 0; i < len; i++) { T[] inner = source[i]; int innerLength = inner.Length; T[] newer = new T[innerLength]; Array.Copy(inner, newer, innerLength); dest[i] = newer; } return dest; } } public class IntLargeComparer : IComparer { public static IntLargeComparer Instance = new IntLargeComparer(); public int Compare(int x, int y) { return y - x; } } public class LongLargeComparer : IComparer { public static LongLargeComparer Instance = new LongLargeComparer(); public int Compare(long x, long y) { if (x > y) return -1; if (x < y) return 1; return 0; } } public static class UtakaExtentions { /// /// 配列をコピーします /// public static T[] Copy(this IList a) { T[] ret = new T[a.Count]; for (int i = 0; i < a.Count; i++) ret[i] = a[i]; return ret; } } public class ConsoleInput { private readonly char _separator = ' '; private readonly TextReader _stream; private readonly Queue inputStream; public ConsoleInput(TextReader stream, char separator = ' ') { _separator = separator; _stream = stream; inputStream = new Queue(); } public string Read { get { if (inputStream.Count != 0) { return inputStream.Dequeue(); } var tmp = _stream.ReadLine().Split(_separator); for (var i = 0; i < tmp.Length; ++i) { inputStream.Enqueue(tmp[i]); } return inputStream.Dequeue(); } } public string ReadLine => _stream.ReadLine(); public int ReadInt => int.Parse(Read); public long ReadLong => long.Parse(Read); public double ReadDouble => double.Parse(Read); public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) { ret[i] = Read; } return ret; } public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) { ret[i] = ReadInt; } return ret; } public int[] ReadIntArrayMinus1(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) { ret[i] = ReadInt - 1; } return ret; } public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) { ret[i] = ReadLong; } return ret; } } public interface IConsole { void Flush(); void Write(object obj); void Write(string str); void WriteLine(object obj); void WriteLine(string str); void WriteLine(); } public class MyConsole : IConsole { public MyConsole() { var sw = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false}; Console.SetOut(sw); } public void Flush() { Console.Out.Flush(); } public void Write(object obj) { Write(obj.ToString()); } public void Write(string str) { Console.Write(str); } public void WriteLine(object obj) { WriteLine(obj.ToString()); } public void WriteLine(string str) { Console.WriteLine(str); } public void WriteLine() { Console.WriteLine(); } } #if UTAKA_LOCAL public class DebugConsole : IConsole { private readonly StringBuilder mSb; public DebugConsole() { mSb = new StringBuilder(); } public void Flush() { // 何もしない } public void Write(object obj) { Write(obj.ToString()); } public void Write(string str) { mSb.Append(str); } public void WriteLine(object obj) { WriteLine(obj.ToString()); } public void WriteLine(string str) { mSb.AppendLine(str); } public void WriteLine() { mSb.AppendLine(); } public string GetAllOutput() { return mSb.ToString(); } } #endif #if UTAKA_LOCAL public class TestCaseCheckerForAtCoder { private string GetDirectoryPath() { var problemPart = string.IsNullOrEmpty(Program.ProblemName) ? "" : $"/{Program.ProblemName}"; return $"{Environment.GetFolderPath(Environment.SpecialFolder.UserProfile)}/AlgorithmPrac/{Program.SiteName}/{Program.ContestName}{problemPart}"; } private string GetInputFilePath(int testCaseNumber) { return $"{GetDirectoryPath()}/sample-{testCaseNumber}.in"; } private string GetOutputFilePath(int testCaseNumber) { return $"{GetDirectoryPath()}/sample-{testCaseNumber}.out"; } public bool TestProblem(int testCaseNumber) { var inputFilePath = GetInputFilePath(testCaseNumber); var outputFilePath = GetOutputFilePath(testCaseNumber); TextReader inputStream = new StreamReader(inputFilePath); var cin = new ConsoleInput(inputStream); var debugConsoleWriter = new DebugConsole(); new Program(cin, debugConsoleWriter).Solve(); var output = debugConsoleWriter.GetAllOutput(); TextReader outputStream = new StreamReader(outputFilePath); var outputAnswer = outputStream.ReadToEnd(); Dbg.WriteLine(output); Dbg.WriteLine(outputAnswer); var isCorrect = output == outputAnswer; return isCorrect; } public void TestProblems(int targetTestCaseNumber = -1) { if (targetTestCaseNumber >= 0) { Console.WriteLine($"!!!!!!!!!!!! Check TestCase {targetTestCaseNumber} !!!!!!!!!!"); } bool isSuccessAll = true; int testCaseNumber = 0; while (true) { testCaseNumber++; bool foundTargetTest = targetTestCaseNumber == testCaseNumber; if (targetTestCaseNumber >= 0 && !foundTargetTest) { continue; } var inputFileName = GetInputFilePath(testCaseNumber); if (!File.Exists(inputFileName)) { break; } Console.WriteLine($"TestCase {testCaseNumber} ====================================================="); var result = TestProblem(testCaseNumber); if (result) { Console.WriteLine("Success"); } else { isSuccessAll = false; Console.WriteLine("Failure *****"); } if (foundTargetTest) { break; } } if (isSuccessAll) { Console.WriteLine("!!!!!!!!! All Success !!!!!!!!!"); } } } #endif public static class Dbg { [Conditional("UTAKA_DEBUG")] public static void WriteLine(string str) { Console.WriteLine(str); } [Conditional("UTAKA_DEBUG")] public static void WriteLine() { Console.WriteLine(); } [Conditional("UTAKA_DEBUG")] public static void Write(string str) { Console.Write(str); } } }