문제
수직선으로 표현될 수 있는 도로에 N개의 트럭이 있으며, 각 정수점에 도시들이 위치하고 있다. 모든 트럭들은 같은 속도로 이동하고 있으며, 어떤 트럭도 정지하고 있지 않다. 각 트럭은 1의 거리를 이동하는데 1분이 걸린다.
당신은 각 트럭의 경로를 알고 있다. 모든 트럭은 같은 시간에 출발하며, 각 트럭의 경로는 A1, A2, ... , Ak 의 k개의 도시로 표현된다. A1으로부터 시작해, A2로 이동하고, A3로 이동하고, 이 과정을 반복한다. 또한, A1 < A2 > A3 < A4 > ... 또는 A1 > A2 < A3 > A4 < ... 이 보장된다. 트럭이 도는데 걸리는 시간은 무시할 수 있다. 트럭이 목적지에 도착한 순간, 외계인들이 나타나 트럭은 사라진다.
M개의 트럭 쌍에 대해, 우리는 도로에서 트럭들이 만난 횟수를 구하고 싶다. 두 트럭이 만난 점이 정수가 아닐 수 있음에 유의하여라.
각 쌍의 트럭들에 대하여 외계인이 데려가는 순간과 출발하는 순간, 방향을 바꾸는 순간에 같은 위치에 있지 않음이 보장된다.
입력
N, M 이 첫 줄에 주어진다. (N, M<=10^5)
두번째 줄부터 N개의 줄에 Ki, Ai1, Ai2, ... AiKi가 주어진다. Ki는 i번째 트럭의 경유점의 개수, Aij는 i번째 트럭의 j번째 경유점을 의미한다. (2<=Ki<=3*10^5, 1<=Aij<=10^9, Ki의 합 <= 3*10^5)
M개의 줄에 걸쳐 같은 위치에 있는 횟수를 구할 두 트럭 a, b가 주어진다.
출력
M개의 줄에 각 쌍별 트럭들이 만나는 횟수를 출력하여라.
예제 #1
3 3
3 1 3 1
2 2 1
3 3 1 3
1 2
2 3
3 1
1
0
2
예제 #2
2 1
4 1 6 3 6
7 3 4 2 6 5 6 1
1 2
3
예제 #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
로그인해야 코드를 작성할 수 있어요.