题目描述

译自 COCI 2014.11.29 T6. KAMIONI

有一条马路，我们将其视为一条数轴。马路上有 $N$ 辆卡车，开始时，卡车都在整点上。所有卡车一起开始移动，并且都以同样的速率移动。没有卡车保持静止。每辆卡车花 $1$ 分钟可以移动 $1$ 个单位距离。

给出每辆卡车的「路线」。路线用一个含有 $k$ 个元素的数组 $A_1,A_2,\dots,A_k$ 表示。该卡车首先 $A_1$ 开往 $A_2$，然后立即掉头开往 $A_3$，以此类推。忽略掉头的耗时。考虑到卡车会掉头，我们保证：

$$A_1 < A_2 > A_3 < A_4 > \dots\ \mathrm{or}\ A_1 > A_2 < A_3 > A_4 < \dots $$

一条可能的路线为 $2→5→1→7$（给出的点要么是起点，要么是终点，要么就是掉头的位置）。开始时卡车位于 $2$，出发 $3$ 分钟后到达位置 $5$，接着掉头。卡车继续行驶到位置 $1$ ，此时距出发已过去了 $7$ 分钟。卡车再次掉头，并行驶到位置 $7$，此时距出发已经经过了 $13$ 分钟。

当卡车到达路线终点后，会有神秘的外星人出现并把它带回飞船。

给出这 $N$ 辆卡车的路线。现在有 $M$ 组询问，每组询问包含两辆卡车。对于每组询问，请回答这对卡车出现在同一位置的次数。位置不一定是整数，比如它们可以在位置 $2.5$ 相遇。

请注意，保证每一对询问的（而不是随便一对）卡车：

• 其中一个被外星人带走的时候，它们不会在同一位置。
• 它们不会在初始时刻或是其中一个转弯的时候在同一位置。

输入格式

第一行，两个整数 $N$ 和 $M(1 \le N \le 10^5,1 \le M \le 10^5)$，表示卡车的数量和询问的卡车的对数。

以下 $N$ 行，其中第 $i$ 行表示第 $i$ 辆卡车的路线。
每行第一个整数 $K_i(1 \le K_i \le 3 \cdot 10^5)$ 表示路线的长度。紧接着是 $K_i$ 个整数 $A_j(1 \le A_j \le 10^9)$，表示卡车 $i$ 路线上的点。给出的点要么是起点，要么是终点，要么就是掉头的位置。
所有卡车移动的总路程之和不会超过 $3 \cdot 10 ^5$。

以下 $M$ 行，其中第 $i$ 行包含两个整数 $(a_i,b_i)$，表示第 $i$ 个询问的两辆卡车。

输出格式

输出 $M$ 行，第 $i$ 行包含我们询问的第 $i$ 对卡车相遇的次数。

3 3
3 1 3 1
2 2 1
3 3 1 3
1 2
2 3
3 1

1
0
2

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

3

3 4
3 1 4 2
4 3 4 2 4
3 4 1 3
1 2
2 3
3 1
1 3

2
1
2
2

数据范围与提示

对于 $50\%$ 的数据，保证 $N \le 10^2,K_i \le 10^3,M \le 10^3$。