Кольцевой мир
Кольцевой мир
Мир на самом деле не является ни диском, ни сферой. Мир - это кольцо! В нем m городов, пронумерованных 0, 1, 2, ..., m - 1, и расположенных по кольцу в естественном порядке: сначала 0, потом 1, затем 2, ..., потом m - 1, и снова 0 (мир - это кольцо, помните?). Вам дается набор непрерывных отрезков городов. Каждый из них начинается в некотором городе x, и содержит города x + 1, x + 2, ..., y - 1, y, для некоторого города y. Обратите внимание, что отрезки могут заворачиваться, например если m = 5, то [3, 4, 0] является допустимым, такими же являются [1], [2, 3, 4] и даже [3, 4, 0, 1, 2].
Ваша задача заключается в выборе одного города внутри каждого отрезка так, чтобы ни один город не был выбран дважды в двух разных отрезках.
Входные данные
Первая строка содержит количество тестов t (1 ≤ t ≤ 20). Каждый тест состоит из набора строк. Первая строка содержит два целых числа m (1 ≤ m ≤ 109
) и n (1 ≤ n ≤ 105
) указывающих на количество городов и запросов соответственно. Следующие n строк задают отрезки: i-ая строка содержит два целых числа xi
, yi
(0 ≤ xi
, yi
< m), описывающих i-ый отрезок [xi
, xi+1
mod m, ..., yi
].
Выходные данные
Для каждого теста вывести в отдельной строке YES, если можно присвоить каждому интервалу уникальный город, и NO иначе.
4 3 3 0 1 1 2 2 0 200000 3 100000 100000 100001 100001 100000 100001 6 6 0 1 1 2 2 3 3 4 4 5 5 0 6 6 0 0 1 2 2 3 4 4 4 5 5 0
YES NO YES NO