まず率直に思いつく方法として、イベント順に解くことを考えると、
$\mathrm{Pair}[i]=[j_1,j_2,...]$：人 $i$ とのクエリがある人 $j$ のリスト
$\mathrm{LastEnter}[i]$：人 $i$ が最後に入った時刻、退室中は $-1$
を用意して、$T_i$ 順に入退室を見ていき、
人 $P_i$ の入室時：
人 $P_i$ の退室時：
としていくと、答えとなる。
問題は、「入退室が多く、ペアも多い人」がいると、$O(NM)$ かかってしまう。
（例えば、ほぼ人 $i$ の入退室で $M$ 個の記録が占められ、クエリでも他の $N-1$ 人全てとの答えが求められる場合など）
そういう人は、別処理をする。
入退室の多い1人を $p$ とする。
記録 $i$ から $i+1$ までの時間を、「時区間 $i$」とする。
各時区間の長さ $D_i=T_{i+1}-T_i$ を求めておく。
長さ $M-1$ の数列 $X$ を用意し、時区間 $i$ に人 $p$ が入室しているなら $X_i=D_i$、退室中は $X_i=0$ とする。
記録 i 0 1 2 3 4 5 6 7
T 3 9 15 17 20 25 26 30
D 6 6 2 3 5 1 4
pの入退室 in out in out
X 6 6 0 0 5 1 0
こうしておけば、
$p$ とペアとなる各人 $j$ につき、
$j$ の各入退室時刻 $(s,t)$（時刻 $T_i$ でなく、記録index $i$ の方で）につき、
全入退室にわたる総和を取れば、$(p,j)$ の答えとなる。
人 $p$ の入退室回数を $R_p$、クエリで $p$ とペアとなる人の数を $P_p$ とする。
イベント順の解法では、$p$ の入退室によって発生する計算量が
「入退室回数 $R_p \times$ ペア数 $P_p$」かかっていたのに比べ、
1人を基準にする解法は最初に $X$ を作る際の「入退室記録数 $M$」の計算量で済む。
相手 $j$ の入退室によって発生する、$p$ の状態確認
（イベント順なら $\mathrm{LastEnter}$ のチェック、1人を基準にする解法なら $X$ の累積和の取得）
の計算量は $R_j$ に依存し、こちらはどちらの解法も変わらない。
よって、「$R_p \times P_p$ が $M$ を超える場合」に、
イベント順から $p$ を基準に解く解法に変えるのが良い、はず。
（以下、駄文）
なお、クエリ $(p,j)$ の両方とも $R_{\circ} \times P_{\circ}$ が大きい場合、
基準とする方をどちらか一方に決めなければいけない。
（どちらでもACできるだろうので別に突き詰める必要は無いのだが）どちらを基準とした方がよいか？
「入退室回数 $R_{\circ}$ が多い」方を基準にした方が、$(p,j)$ ペアだけ考えたときの削減効果は大きいが、
基準にされなかった方は、実質的に $P_{\circ}$（※）が1減り、評価値 $R_{\circ} \times P_{\circ}$ が変動する。
（※イベント順の解法を取ったときに、入退室のたびにチェックする相手数）
評価値 $R_{\circ} \times P_{\circ}$ が減ることで、結局イベント順の解法にした方がいい、となるかもしれない。
その場合、評価値の削減効果が大きいのも「入退室回数 $R_{\circ}$ が多い」方である。
この最適化って、どうしたらいいんだろうね。
Python3
from collections import defaultdict
from itertools import accumulate
n, m = map(int, input().split())
events = []
in_out = [[] for _ in range(n)]
section_times = []
for i in range(m):
t, p = map(int, input().split())
p -= 1
if i > 0:
section_times.append(t - events[-1][0])
if len(in_out[p]) == 0 or in_out[p][-1][1] != -1:
in_out[p].append([i, -1])
events.append((t, p, 0))
else:
in_out[p][-1][1] = i
events.append((t, p, 1))
q = int(input())
queries = defaultdict(list)
for qi in range(q):
a, b = map(int, input().split())
a -= 1
b -= 1
queries[a, b].append(qi)
unique_queries = list(queries.keys())
pair_count = [0] * n
for a, b in unique_queries:
pair_count[a] += 1
pair_count[b] += 1
THRESHOLD = 200000 # 入退室回数 × クエリペア数
event_pairs = [[] for _ in range(n)]
hub_pairs = {i: [] for i in range(n) if len(in_out[i]) * pair_count[i] >= THRESHOLD}
for uqi, (a, b) in enumerate(unique_queries):
if a in hub_pairs:
hub_pairs[a].append((b, uqi))
elif b in hub_pairs:
hub_pairs[b].append((a, uqi))
else:
event_pairs[a].append((b, uqi))
event_pairs[b].append((a, uqi))
unique_ans = [0] * len(unique_queries)
for i, pairs in hub_pairs.items():
timeline = [0] * m
for s, t in in_out[i]:
for ti in range(s, t):
timeline[ti + 1] = section_times[ti]
timeline = list(accumulate(timeline))
for j, uqi in pairs:
tmp = 0
for s, t in in_out[j]:
tmp += timeline[t] - timeline[s]
unique_ans[uqi] = tmp
last_enter = [-1] * n # 在席していれば最終入室時刻、してなければ-1
for t, i, io in events:
if io == 0:
last_enter[i] = t
continue
lei = last_enter[i]
last_enter[i] = -1
for j, uqi in event_pairs[i]:
if last_enter[j] == -1:
continue
unique_ans[uqi] += t - max(lei, last_enter[j])
ans = [0] * q
for uqi, ab in enumerate(unique_queries):
for qi in queries[ab]:
ans[qi] = unique_ans[uqi]
print('\n'.join(map(str, ans)))