시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 16 4 4 40.000%

문제

링월드는 반지모양으로 이루어진 나라이다. 이 나라에는 도시가 m개 있고, 편의상 0, 1, 2, ... m-1로 번호가 매겨져 있다. 이 도시는 반지모양을 이루고 있으며, 0, 1, 2, m-1, 그리고 다시 0 순서이다.

연속된 도시의 구간 n개가 주어진다. 각 구간은 도시 x에서 시작하며, x, x+1, x+2, ..., y 까지 도시를 포함한다. m = 5인 경우에 [3, 4, 0], [1], [2,3,4], [3,4,0,1,2]는 모두 올바른 도시 구간이다.

각 구간에서 도시를 하나씩 고르려고 한다. 한 도시가 두 구간에서 선택될 수 없다. 즉, 한 구간에서 도시 i를 골랐으면, 다른 구간에서는 도시 i를 고를 수 없다. 각 구간에서 도시를 하나씩 고르는 것이 가능한지 불가능한지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 1 ≤ T ≤ 20가 주어진다.

각 테스트 케이스의 첫재 줄에는 도시의 수 1 ≤ m ≤ 109 과 구간의 수 1 ≤ n ≤ 105이 주어진다.

다음 n개 줄에는 구간의 시작 도시 xi와 끝 도시 yi가 주어지며, 구간 [xi, xi + 1 mod m, ..., yi]를 나타낸다.

출력

각 테스트 케이스에 대해서, 각 구간별로 서로 다른 도시를 선택하는 것이 가능하면 YES, 불가능하면 NO를 출력한다.

예제 입력 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

예제 출력 1

YES
NO
YES
NO
W3sicHJvYmxlbV9pZCI6IjkyMDgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5YzFcdWM2ZDRcdWI0ZGMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjljMVx1YzZkNFx1YjRkY1x1YjI5NCBcdWJjMThcdWM5YzBcdWJhYThcdWM1OTFcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YjA5OFx1Yjc3Y1x1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YjA5OFx1Yjc3Y1x1YzVkMFx1YjI5NCBcdWIzYzRcdWMyZGNcdWFjMDAgbVx1YWMxYyBcdWM3ODhcdWFjZTAsIFx1ZDNiOFx1Yzc1OFx1YzBjMSAwLCAxLCAyLCAuLi4gbS0xXHViODVjIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViM2M0XHVjMmRjXHViMjk0IFx1YmMxOFx1YzljMFx1YmFhOFx1YzU5MVx1Yzc0NCBcdWM3NzRcdWI4ZThcdWFjZTAgXHVjNzg4XHVjNzNjXHViYTcwLCAwLCAxLCAyLCBtLTEsIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWIyZTRcdWMyZGMgMCBcdWMyMWNcdWMxMWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzVmMFx1YzE4ZFx1YjQxYyBcdWIzYzRcdWMyZGNcdWM3NTggXHVhZDZjXHVhYzA0IG5cdWFjMWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVhZDZjXHVhYzA0XHVjNzQwIFx1YjNjNFx1YzJkYyB4XHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YmE3MCwgeCwgeCsxLCB4KzIsIC4uLiwgeSBcdWFlNGNcdWM5YzAgXHViM2M0XHVjMmRjXHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1Y1x1YjJlNC4gbSA9IDVcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwIFszLCA0LCAwXSwgWzFdLCBbMiwzLDRdLCBbMyw0LDAsMSwyXVx1YjI5NCBcdWJhYThcdWI0NTAgXHVjNjJjXHViYzE0XHViOTc4IFx1YjNjNFx1YzJkYyBcdWFkNmNcdWFjMDRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWFkNmNcdWFjMDRcdWM1ZDBcdWMxMWMgXHViM2M0XHVjMmRjXHViOTdjIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWFjZTBcdWI5NzRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWQ1NWMgXHViM2M0XHVjMmRjXHVhYzAwIFx1YjQ1MCBcdWFkNmNcdWFjMDRcdWM1ZDBcdWMxMWMgXHVjMTIwXHVkMGRkXHViNDIwIFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1Yzk4OSwgXHVkNTVjIFx1YWQ2Y1x1YWMwNFx1YzVkMFx1YzExYyBcdWIzYzRcdWMyZGMgaVx1Yjk3YyBcdWFjZThcdWI3OTBcdWM3M2NcdWJhNzQsIFx1YjJlNFx1Yjk3OCBcdWFkNmNcdWFjMDRcdWM1ZDBcdWMxMWNcdWIyOTQgXHViM2M0XHVjMmRjIGlcdWI5N2MgXHVhY2UwXHViOTdjIFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YWMwMSBcdWFkNmNcdWFjMDRcdWM1ZDBcdWMxMWMgXHViM2M0XHVjMmRjXHViOTdjIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWFjZTBcdWI5NzRcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YWMwMFx1YjJhNVx1ZDU1Y1x1YzljMCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NWNcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IDEgJmxlOyBUICZsZTsgMjBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM3YWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWMyMTggMSAmbGU7IG0gJmxlOyAxMDxzdXA+OTxcL3N1cD4gXHVhY2ZjIFx1YWQ2Y1x1YWMwNFx1Yzc1OCBcdWMyMTggMSAmbGU7IG4gJmxlOyAxMDxzdXA+NTxcL3N1cD5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgblx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZDZjXHVhYzA0XHVjNzU4IFx1YzJkY1x1Yzc5MSBcdWIzYzRcdWMyZGMgeDxzdWI+aTxcL3N1Yj5cdWM2NDAgXHViMDVkIFx1YjNjNFx1YzJkYyB5PHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YWQ2Y1x1YWMwNCBbeDxzdWI+aTxcL3N1Yj4sIHg8c3ViPmk8XC9zdWI+ICsgMSBtb2QgbSwgLi4uLCB5PHN1Yj5pPFwvc3ViPl1cdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVhYzAxIFx1YWQ2Y1x1YWMwNFx1YmNjNFx1Yjg1YyBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YWMwMFx1YjJhNVx1ZDU1OFx1YmE3NCBZRVMsIFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1OFx1YmE3NCBOT1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTIwOCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJpbmd3b3JsZCIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIHdvcmxkIGlzIGFjdHVhbGx5IG5laXRoZXIgYSBkaXNjIG9yIGEgc3BoZXJlLiBJdCBpcyBhIHJpbmchIFRoZXJlIGFyZSBtIGNpdGllcyB0aGVyZSwgY29udmVuaWVudGx5IGNhbGxlZCAwLCAxLCAyLC4uLiAsIG0gLSAxLCBhbmQgYXJyYW5nZWQgb24gdGhlIHJpbmcgaW4gdGhlIG5hdHVyYWwgb3JkZXI6IGZpcnN0IDAsIHRoZW4gMSwgdGhlbiAyLCAuLi4sIHRoZW4gbSAtIDEsIGFuZCB0aGVuIGFnYWluIDAgKGFzIHRoZSB3b3JsZCBpcyBhIHJpbmcsIHJlbWVtYmVyPykuIFlvdSBhcmUgZ2l2ZW4gYSBjb2xsZWN0aW9uIG9mIGNvbnRpZ3VvdXMgcmFuZ2VzIG9mIGNpdGllcy4gRWFjaCBvZiB0aGVtIHN0YXJ0cyBhdCBzb21lIGNpdHkgeCwgYW5kIGNvbnRhaW5zIGFsc28gY2l0aWVzIHggKyAxLCB4ICsgMiwgLi4uLCB5IC0gMSwgeSwgZm9yIHNvbWUgY2l0eSB5LiBOb3RlIHRoYXQgdGhlIHJhbmdlIGNhbiB3cmFwIGFyb3VuZCwgZm9yIGluc3RhbmNlIGlmIG0gPSA1LCB0aGVuIFszLDQsMF0gaXMgYSB2YWxpZCByYW5nZSwgYW5kIHNvIGFyZSBbMV0sIFsyLDMsNF0sIG9yIGV2ZW4gWzMsNCwwLDEsMl0uIFlvdXIgdGFzayBpcyB0byBjaG9vc2UgYSBzaW5nbGUgY2l0eSBpbnNpZGUgZWFjaCByYW5nZSBzbyB0aGF0IG5vIGNpdHkgaXMgY2hvc2VuIHR3aWNlIGZvciB0d28gZGlmZmVyZW50IHJhbmdlcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBzZXZlcmFsIGxpbmVzLiBUaGUgZmlyc3QgbGluZSBjb250YWlucyAxICZsZTsgVCAmbGU7IDIwLCB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuJm5ic3A7PHNwYW4gc3R5bGU9XCJsaW5lLWhlaWdodDoxLjZlbVwiPkVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIGEgbnVtYmVyIG9mIGxpbmVzLiBUaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgMSAmbGU7IG0gJmxlOyAxMDxzdXA+OTxcL3N1cD4gYW5kIDEgJmxlOyBuICZsZTsgMTA8c3VwPjU8XC9zdXA+IGRlbm90aW5nIHRoZSBudW1iZXIgb2YgY2l0aWVzIGFuZCB0aGUgbnVtYmVyIG9mIHJlcXVlc3RzLCByZXNwZWN0aXZlbHkuIFRoZSBuZXh0IG4gbGluZXMgZGVmaW5lIHRoZSByYW5nZXM6IHRoZSBpLXRoIHJvdyBjb250YWlucyB0d28gaW50ZWdlcnMgMCAmbGU7IHg8c3ViPmk8XC9zdWI+LCB5PHN1Yj5pPFwvc3ViPiAmbHQ7IG0gZGVzY3JpYmluZyB0aGUgaS10aCByYW5nZSBbeDxzdWI+aTxcL3N1Yj4sIHg8c3ViPmk8XC9zdWI+ICsgMSBtb2QgbSwgLi4uLCB5PHN1Yj5pPFwvc3ViPl0uPFwvc3Bhbj48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBvbmUgbGluZSBjb250YWluaW5nIFlFUyBpZiBpdCBpcyBwb3NzaWJsZSB0byBhc3NpZ24gYSB1bmlxdWUgY2l0eSB0byBlYWNoIHJlcXVlc3QsIGFuZCBOTyBvdGhlcndpc2UuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d