P4811 [COCI 2014/2015 #3] KAMIONI

**译自 [COCI 2014/2015 Contest 3](http://www.hsin.hr/coci/archive/2014_2015/) 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$ 分钟。 当卡车到达路线终点后，会有神秘的 ~~Planet6174~~ 外星人出现并把它带回飞船。 给出这 $N$ 辆卡车的路线。现在有 $M$ 组询问，每组询问包含两辆卡车。对于每组询问，请回答这对卡车出现在同一位置的次数。位置不一定是整数，比如它们可以在位置 $2.5$ 相遇。 请注意，保证每一对**询问的**（而不是随便一对）卡车： - 其中一个被 ~~Planet6174~~ 外星人带走的时候，它们不会在同一位置。 - 它们不会在初始时刻或是其中一个转弯的时候在同一位置。 > Planet6174：翻译这道题目的人已经被解决掉了（滑稽

第一行，两个整数 $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$ 对卡车相遇的次数。

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