A - Two in the Range Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 800 点

問題文

整数 N と，1\leq L_i<R_i\leq N を満たす M 個の整数の組 (L_1,R_1),(L_2,R_2),\ldots,(L_M,R_M) が与えられます．

長さ N の 0,1 列 x=(x_1,x_2,\ldots,x_N) であって，以下の条件をすべて満たすものが存在するか判定してください．

  • すべての i=1,2,\ldots,M について，x_{L_i}+x_{L_i+1}+\cdots+x_{R_i}=2 である．

T 個のテストケースが与えられるので，それぞれについて答えてください．

制約

  • 1\leq T\leq 250000
  • 2\leq N\leq 500000
  • 1\leq M\leq 500000
  • 1\leq L_i<R_i\leq N (1 \leq i \leq M)
  • すべてのテストケースにわたる N の総和は 500000 以下
  • すべてのテストケースにわたる M の総和は 500000 以下
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる．

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケースは以下の形式で与えられる．

N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M

出力

T 行出力せよ．i 行目には，i 番目のテストケースについて，条件を満たす列が存在する場合は Yes，存在しない場合は No と出力せよ．

入力例 1

6
3 3
1 2
2 3
1 3
10 5
1 4
3 7
6 10
1 4
2 6
2 1
1 2
4 3
1 3
3 4
2 4
4 3
1 2
3 4
1 4
5 3
1 5
1 5
1 5

出力例 1

No
Yes
Yes
Yes
No
Yes

1 番目のテストケースでは，最初の 2 個の条件から x_1=x_2=x_3=1 となりますが，これは 3 個目の条件を満たしません． よって，条件を満たす列は存在しません．

2 番目のテストケースでは，x=(0,1,0,1,0,0,1,0,1,0) とすると，指定された区間 [1,4],[3,7],[6,10],[1,4],[2,6] の和はいずれも 2 になります． よって，この列はすべての条件を満たします．

Score : 800 points

Problem Statement

You are given an integer N, and M pairs of integers (L_1,R_1),(L_2,R_2),\ldots,(L_M,R_M) satisfying 1\leq L_i<R_i\leq N.

Determine whether there exists a length-N sequence of 0s and 1s, x=(x_1,x_2,\ldots,x_N), that satisfies all of the following conditions.

  • x_{L_i}+x_{L_i+1}+\cdots+x_{R_i}=2 for every i=1,2,\ldots,M.

You are given T test cases; solve each of them.

Constraints

  • 1\leq T\leq 250000
  • 2\leq N\leq 500000
  • 1\leq M\leq 500000
  • 1\leq L_i<R_i\leq N (1 \leq i \leq M)
  • The sum of N over all test cases is at most 500000.
  • The sum of M over all test cases is at most 500000.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M

Output

Output T lines. The i-th line should contain Yes if a sequence satisfying the conditions exists for the i-th test case, and No otherwise.

Sample Input 1

6
3 3
1 2
2 3
1 3
10 5
1 4
3 7
6 10
1 4
2 6
2 1
1 2
4 3
1 3
3 4
2 4
4 3
1 2
3 4
1 4
5 3
1 5
1 5
1 5

Sample Output 1

No
Yes
Yes
Yes
No
Yes

In the first test case, the first two conditions imply x_1=x_2=x_3=1, but then the third condition is not satisfied. Thus, no sequence satisfies the conditions.

In the second test case, if x=(0,1,0,1,0,0,1,0,1,0), the sums over the specified intervals [1,4],[3,7],[6,10],[1,4],[2,6] are all 2. Thus, this sequence satisfies all the conditions.