{"problem":{"name":"E. Ringworld","description":{"content":"The world is actually neither a disc or a sphere. It is a ring! There are m cities there, conveniently called 0, 1, 2, ..., m - 1 and arranged on the ring in the natural order: first 0, then 1, then 2","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":131072},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10031E"},"statements":[{"statement_type":"Markdown","content":"The world is actually neither a disc or a sphere. It is a ring! There are m cities there, conveniently called 0, 1, 2, ..., m - 1 and arranged on the ring in the natural order: first 0, then 1, then 2, ..., then m - 1, and then again 0 (as the world is a ring, remember?). You are given a collection of contiguous ranges of cities. Each of them starts at some city x, and contains also cities x + 1, x + 2, ..., y - 1, y, for some city y. Note that the range can wrap around, for instance if m = 5, then [3, 4, 0] is a valid range, and so are [1], [2, 3, 4], or even [3, 4, 0, 1, 2]. Your task is to choose a single city inside each range so that no city is chosen twice for two different ranges.\n\nThe input consists of several lines. The first line contains 1 ≤ T ≤ 20, the number of test cases.\n\nEach test case consists of a number of lines. The first line contains two integers 1 ≤ m ≤ 109 and 1 ≤ n ≤ 105 denoting the number of cities and the number of requests, respectively. The next n lines define the ranges: the i-th row contains two integers 0 ≤ xi, yi < m describing the i-th range .\n\nFor each test case, output one line containing YES if it is possible to assign a unique city to each request, and NO otherwise.\n\n## Input\n\nThe input consists of several lines. The first line contains 1 ≤ T ≤ 20, the number of test cases.Each test case consists of a number of lines. The first line contains two integers 1 ≤ m ≤ 109 and 1 ≤ n ≤ 105 denoting the number of cities and the number of requests, respectively. The next n lines define the ranges: the i-th row contains two integers 0 ≤ xi, yi < m describing the i-th range .\n\n## Output\n\nFor each test case, output one line containing YES if it is possible to assign a unique city to each request, and NO otherwise.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ m \\in \\mathbb{Z} $ be the number of cities, labeled $ \\{0, 1, \\dots, m-1\\} $ arranged cyclically.  \n- Let $ n \\in \\mathbb{Z} $ be the number of ranges.  \n- For each $ i \\in \\{1, \\dots, n\\} $, define a circular range $ R_i = [x_i, y_i] $ as the set of cities obtained by starting at $ x_i $, moving clockwise, and including all cities up to and including $ y_i $, wrapping around if necessary.  \n\nFormally, $ R_i = \\{ (x_i + k) \\mod m \\mid k = 0, 1, \\dots, \\ell_i \\} $, where $ \\ell_i = (y_i - x_i) \\mod m $, and the size of $ R_i $ is $ |R_i| = (\\ell_i + 1) \\mod m $, with $ |R_i| \\geq 1 $.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 20 $  \n2. For each test case:  \n   - $ 1 \\leq m \\leq 10^9 $  \n   - $ 1 \\leq n \\leq 10^5 $  \n   - $ 0 \\leq x_i, y_i < m $ for all $ i \\in \\{1, \\dots, n\\} $  \n\n**Objective**  \nDetermine whether there exists an injective function $ f: \\{1, \\dots, n\\} \\to \\{0, 1, \\dots, m-1\\} $ such that $ f(i) \\in R_i $ for all $ i \\in \\{1, \\dots, n\\} $.  \nOutput YES if such an assignment exists; otherwise, output NO.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10031E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}