링월드

시간 제한2초메모리 제한128 MB

요약

m개 도시가 고리로 이어진 나라에서 n개 연속 구간마다 서로 겹치지 않는 도시 하나를 고를 수 있는지 판정합니다.

난이도: 어려움10점 중 8점
유형: 그리디, 구간, 정렬
정답자: 아직 제출이 없습니다

문제

링월드는 고리 모양으로 생긴 나라이다. 도시가 $m$ 개 있고 $0, 1, 2, \dots, m-1$ 로 번호가 붙어 있다. 도시는 $0, 1, 2, \dots, m-1$ 순서로 이어지고 $m-1$ 다음에 다시 $0$ 이 오는 고리를 이룬다.

연속한 도시로 이루어진 구간 $n$ 개가 주어진다. 각 구간은 도시 $x$ 에서 시작해 $x, x+1, x+2, \dots, y$ 까지의 도시를 포함하고, $m-1$ 다음은 $0$ 으로 이어진다. $m = 5$ 일 때 $[3, 4, 0]$ , $[1]$ , $[2, 3, 4]$ , $[3, 4, 0, 1, 2]$ 는 모두 올바른 구간이다.

각 구간에서 도시를 하나씩 고르려고 한다. 한 도시를 두 구간에서 고를 수는 없다. 즉, 어떤 구간에서 도시 $i$ 를 골랐다면 다른 구간에서는 도시 $i$ 를 고를 수 없다. 모든 구간에서 서로 다른 도시를 하나씩 고르는 것이 가능한지 판정하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 $T$ ( $1 \le T \le 20$ )가 주어진다.

각 테스트 케이스의 첫째 줄에는 도시의 수 $m$ ( $1 \le m \le 10^9$ )과 구간의 수 $n$ ( $1 \le n \le 10^5$ )이 주어진다.

다음 $n$ 개 줄에는 구간의 시작 도시 $x_i$ 와 끝 도시 $y_i$ 가 주어진다 ( $0 \le x_i, y_i \le m-1$ ). 이 줄은 구간 $[x_i, (x_i + 1) \bmod m, \dots, y_i]$ 를 뜻한다.

출력

각 테스트 케이스마다 모든 구간에서 서로 다른 도시를 하나씩 고를 수 있으면 YES를, 고를 수 없으면 NO를 한 줄에 출력한다.

예제1

예제 1

입력

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