\(3^{rd}\) round, November \(29^{th}\), 2014
We are observing the movement of N trucks on the road. The road can be represented as a number line. The
points on the line denoting cities are integers. The cities are denoted with the number of the corresponding point
on the line.
All trucks are moving with the same speed and no single truck is standing still at any given moment.
Each truck takes 1 minute to pass the distance between two adjacent cities.
You are given the route of each truck. All of the trucks start their route at the same initial moment.
The route is given as an array of k cities: A1, A2, ..., A_{k}. The truck starts from city A1 and drives to city A2,
then turns and drives to city A3 and so on. Given the fact that the truck turns, it will hold:
A\(1 < A@@RISE_MATH_BLOCK_0@@3 < A\)4 > ... or A\(1 > A@@RISE_MATH_BLOCK_1@@3 > A\)4 < ...
The time it takes for the truck to turn is negligible.
One possible route is 2, 5, 1, 7. The truck is at city number 2 initially, 3 minutes after departure it arrives to city
number 5. It turns and continues towards the city number 1 in which it arrives 7 minutes after departure. It turns
again and drives towards city number 7 in which it arrives at moment 13.
After the truck completes his route, aliens appear and take it away in their space rocket.
For some pairs of trucks, we want to know the number of times they encountered each other on the road. In other
words, how many times they appeared to be on the same position (the position they encountered doesn’t need to
be an integer; i.e. they could’ve encountered at position 2.5).
Write a programme that will, for a given number of trucks N and their routes and for M pairs of trucks, determine
the number of encounters for each pair.
Please note: each pair of trucks we want to know the number of encounters for, it will hold:
• they won’t be at the same place in the moment when one of them (or both) are being taken away by aliens
• they won’t be at the same place in the initial moment or in the moment when one of them (or both) are
turning
The upper statement won’t hold for all pairs of trucks, but only the pairs we want to know the number of
encounters for.

In the test cases worth 50% of total points, it will hold N ⩽\(10^{2}\), K_{i} ⩽\(10^{3}\), M ⩽\(10^{3}\).
\(3^{rd}\) round, November \(29^{th}\), 2014

The first line of input contains the integers N and M (1 ⩽N ⩽\(10^{5}\), 1 ⩽M ⩽\(10^{5}\)), the number of trucks and the
number of pairs of trucks we want to know the number of encounters for.
The i^{th} of the following N lines contains the description of the route of the i^{th} truck.
The first integer in the line, K_{i} (2 ⩽K_{i} ⩽\(3 \cdot 10^{5}\)) represents the number of cities on the truck’s route. After it K_{i}
integers follow, A_{j} (1 ⩽A_{j} ⩽\(10^{9}\)), the ordinal numbers of the cities on the truck’s route given in the order which
the truck visits them.
The sum of routes of all the trucks won’t exceed \(3 \cdot 10^{5}\).
Each of the following M lines contains two integers (a_{i}, b_{i}), the ordinal numbers of the trucks we want to know
the number of encounters for.

Output M lines. The i^{th} line must contain the number of encounters of the i^{th} pair of trucks from the input.

생성자가 기록되지 않았습니다.

출처 COCI 2014/2015 Contest 3