F - Chord Crossing Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 525 点

問題文

円周上に 2N 個の点が等間隔に並んでおり、ある点から始めて時計回りに 1,2,\dots,2N の番号が付けられています。

これらの点を結ぶ M 本の線分 1,2,\dots,M が存在し、線分 i は点 A_i と点 B_i を結んでいます。 ここで、A_i と B_i は相異なる 偶数 です。 また、これらの線分のうちのどの 2 つの線分も共有点を持たないことが保証されます。

Q 個のクエリを処理してください。j 番目のクエリは以下の通りです。

  • 相異なる 2 つの 奇数 C_j, D_j が与えられる。上で与えられた M 本の線分 1,2,\dots,M のうち、点 C_j と点 D_j を結ぶ線分と共有点を持つものの本数を求めよ。

制約

  • 2\leq N \leq 10^6
  • 1\leq M \leq \min\left(\lfloor\frac{N}{2}\rfloor, 2\times 10^5\right)
  • 1\leq Q \leq 2\times 10^5
  • 1\leq A_i< B_i\leq 2N
  • 1\leq C_j< D_j\leq 2N
  • A_i, B_i は偶数
  • C_j, D_j は奇数
  • どの i_1, i_2\ (i_1 \neq i_2) についても、線分 i_1 と線分 i_2 は共有点を持たない
  • 入力は全て整数

入力

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

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M
Q
C_1 D_1
C_2 D_2
\vdots
C_Q D_Q

出力

Q 行出力せよ。 j\ (1\leq j \leq Q) 行目には、j 番目のクエリに対する答えを出力せよ。

入力例 1

4 2
2 4
6 8
3
1 3
3 7
1 5

出力例 1

1
2
0

上図は入力例 1 を図示したものであり、黒丸は 2N\ (=8) 個の点を、青い実線は最初に与えられる M\ (=2) 本の線分を、赤い点線はクエリで与えられる Q\ (=3) 本の線分をそれぞれ表しています。

  • 1 番目のクエリについて、最初に与えられた M 本の線分のうち、点 1 と点 3 を結ぶ線分と共有点を持つものは線分 1 の 1 本です。
  • 2 番目のクエリについて、最初に与えられた M 本の線分のうち、点 3 と点 7 を結ぶ線分と共有点を持つものは線分 1,2 の 2 本です。
  • 3 番目のクエリについて、最初に与えられた M 本の線分のうち、点 1 と点 5 を結ぶ線分と共有点を持つものは 0 本です。

入力例 2

20 7
24 34
26 28
18 38
2 14
8 12
30 32
20 22
10
7 29
31 39
9 21
19 29
15 21
11 39
17 21
15 31
5 25
25 31

出力例 2

3
3
4
1
2
2
2
3
3
1

Score : 525 points

Problem Statement

On a circle, 2N points are placed at equal intervals and numbered 1,2,\dots,2N in clockwise order starting from an arbitrary point.

There are M line segments numbered 1,2,\dots,M connecting these points. Segment i connects points A_i and B_i. Here, A_i and B_i are distinct even numbers. It is guaranteed that no two of these segments share a point.

Process Q queries. The j‑th query is as follows:

  • You are given two distinct odd numbers C_j and D_j. Among the M segments 1,2,\dots,M, find how many share a point with the segment connecting points C_j and D_j.

Constraints

  • 2 \le N \le 10^6
  • 1\leq M \leq \min\left(\lfloor\frac{N}{2}\rfloor, 2\times 10^5\right)
  • 1 \le Q \le 2 \times 10^5
  • 1 \le A_i < B_i \le 2N
  • 1 \le C_j < D_j \le 2N
  • A_i and B_i are even.
  • C_j and D_j are odd.
  • For any i_1 and i_2 (i_1 \neq i_2), segments i_1 and i_2 do not share a point.
  • All input values are integers.

Input

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

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M
Q
C_1 D_1
C_2 D_2
\vdots
C_Q D_Q

Output

Output Q lines. The j-th line (1\leq j \leq Q) should contain the answer to the j‑th query.

Sample Input 1

4 2
2 4
6 8
3
1 3
3 7
1 5

Sample Output 1

1
2
0

The figure above illustrates Sample Input 1. Black dots are the 2N\ (=8) points, blue solid lines are the initial M\ (=2) segments, and red dashed lines are the Q\ (=3) query segments.

  • For the first query, the segment connecting points 1 and 3 intersects one initial segment: segment 1.
  • For the second query, the segment connecting points 3 and 7 intersects two initial segments: segments 1 and 2.
  • For the third query, the segment connecting points 1 and 5 intersects zero initial segments.

Sample Input 2

20 7
24 34
26 28
18 38
2 14
8 12
30 32
20 22
10
7 29
31 39
9 21
19 29
15 21
11 39
17 21
15 31
5 25
25 31

Sample Output 2

3
3
4
1
2
2
2
3
3
1