Ringworld#6036
The world is actually neither a disc nor a sphere. It is a ring! There are cities, conveniently numbered 0, 1, 2, \ldots, m - 1, arranged on the ring in their natural order: first , then , then , , then m-1, and then again (because the world is a ring, remember?).
You are given a collection of contiguous segments of cities. Each segment starts at some city , and also contains the cities x+1, x+2, , y-1, , for some city . Note that a segment can wrap around the ring; for example, if m = 5, then [3, 4, 0] is a valid segment. So are , [2, 3, 4], or even [3, 4, 0, 1, 2].
Your task is to choose exactly one city within each segment so that no city is chosen more than once for two different segments.
The first line contains the number of test cases (1 \le t \le 20).
Each test case consists of several lines. The first line of a test case contains two integers (1 \le m \le 10^9) and (1 \le n \le 10^5), the number of cities and the number of segments, respectively.
The next lines describe the segments: the -th line contains two integers x_i, y_i (0 \le x_i, y_i < m), which represent the -th segment [x_i, (x_i+1) \bmod m, \ldots, y_i].
For each test case, output a single line containing YES if it is possible to assign a unique city to each segment, and NO otherwise.
Example 1