프로그램 명: coci_kamioni
제한시간: 3 초

N마리의 외계인들이 직선 형태의 고속도로에서 N개의 트럭을 운전한다. 이 트럭들은 이상하게 움직이는데, 항상 1의 속도로 운전하며, 방향을 돌리는 지점의 좌표는 항상 정수이다.

외계인들의 수장인 민준이는 N마리의 외계인들이 트럭을 어떻게 운전하는 지에 대한 정보를 알고 있다. 트럭의 경로는 K개의 정수 A1, A2, …, Ak로 이루어진 수열이며, 아래 정보를 만족한다.

A1 < A2 > A3 < A4 > … 이거나 A1 > A2 < A3 > A4 < …

트럭은 A1에서 시작해서 A2, A3, …, Ak-1에서 방향을 돌린 후 Ak에서 도착하며, 트럭이 도착한 이후에는 UFO가 나타나서 트럭을 올려 보낸다.

어떤 외계인들끼리는 정보를 교환해야 하므로 몇 번 만나는지 알아야 한다. 민준이가 구해야 하는 외계인들의 쌍에 대해서는 아래 조건을 만족한다.

민준이는 가장 똑똑한 지구인인 당신에게 M개의 쌍에 대해서 몇 번 만나는지 구하는 프로그램을 작성해 달라고 요청했다.

입력 형식

전체 데이터의 50%는 N ≤ 100, M, K ≤ 1,000이다.

출력 형식

각 쌍에 대해 외계인들이 만나는 횟수를 한 줄에 하나씩 출력한다.

입출력 예 

입력

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
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, ..., Ak. 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:

A1 < A2 > A3 < A4 > ... or A1 > A2 < A3 > A4 < ...

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:

The upper statement won’t hold for all pairs of trucks, but only the pairs we want to know the number of encounters for. INPUT OUTPUT SCORING In the test cases worth 50% of total points, it will hold N <= 102 , Ki <= 103 , M 6 103 . SAMPLE TESTS

입력

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, Ki (2 <= Ki <= 3 * 10^5) represents the number of cities on the truck’s route. After it Ki integers follow, Aj (1 <= Aj <= 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*10^5 .

Each of the following M lines contains two integers (ai , bi), 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.

입출력 예

입력

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

출처:coci 2013/2014 6/6
번역:functionx
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]