P4811 [COCI 2014/2015 #3] KAMIONI

**Translated from [COCI 2014/2015 Contest 3](http://www.hsin.hr/coci/archive/2014_2015/) T6 "KAMIONI".** There is a road, and we view it as a number line. There are $N$ trucks on the road. Initially, all trucks are at integer points. All trucks start moving at the same time, and they all move at the **same speed**. **No truck stays still.** Each truck can move $1$ unit of distance in $1$ minute. For each truck, its "route" is given. A route is represented by an array $A_1,A_2,\dots,A_k$ with $k$ elements. The truck first drives from $A_1$ to $A_2$, then immediately turns around and drives to $A_3$, and so on. Ignore the time spent on turning around. Since the truck turns around, we guarantee: $$A_1 < A_2 > A_3 < A_4 > \dots\ \mathrm{or}\ A_1 > A_2 < A_3 > A_4 < \dots$$ One possible route is $2→5→1→7$ (the given points are either the start, the end, or turning points). At the beginning the truck is at $2$. After $3$ minutes it reaches position $5$, and then turns around. The truck continues to position $1$; at this time $7$ minutes have passed since it started. The truck turns around again and drives to position $7$; at this time $13$ minutes have passed since it started. When a truck reaches the end of its route, mysterious ~~Planet6174~~ aliens appear and take it back to their spaceship. The routes of these $N$ trucks are given. Now there are $M$ queries, and each query contains two trucks. For each query, output how many times this pair of trucks appears at the same position. The position does not have to be an integer; for example, they can meet at position $2.5$. Note that for every pair of trucks **that is queried** (not an arbitrary pair), it is guaranteed that: - When one of them is taken away by the ~~Planet6174~~ aliens, they are not at the same position. - They are not at the same position at the initial time, nor at the moment when one of them turns around. > Planet6174: The person who translated this problem has already been dealt with (joking).

The first line contains two integers $N$ and $M(1 \le N \le 10^5,1 \le M \le 10^5)$, representing the number of trucks and the number of queried pairs. The next $N$ lines describe the routes. The $i$-th line describes the route of the $i$-th truck. The first integer on the line is $K_i(1 \le K_i \le 3 \cdot 10^5)$, the length of the route. This is followed by $K_i$ integers $A_j(1 \le A_j \le 10^9)$, representing the points on truck $i$'s route. The given points are either the start, the end, or turning points. The total sum of route lengths of all trucks does not exceed $3 \cdot 10 ^ 5$. The next $M$ lines each contain two integers $(a_i,b_i)$, representing the two trucks in the $i$-th query.

Output $M$ lines. The $i$-th line should contain the number of meetings for the $i$-th queried pair of trucks.

For $50\%$ of the testdata, it is guaranteed that $N \le 10^2,K_i \le 10^3,M \le 10^3$. Translated by ChatGPT 5