만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

조류학

면접 대비

시간 제한5초메모리 제한1024 MB

요약
첫 번째 줄에서 두 번째 줄로 날아가는 새들의 선분 중 서로 교차하는 쌍의 개수를 구합니다.
난이도

보통10점 중 4점

유형
배열, 누적 합
정답자
아직 제출이 없습니다

문제

도시 외곽, 농장 가까이에 평행한 전선 두 개가 좁은 흙길을 사이에 두고 놓여 있습니다. 이 전선은 많은 새가 즐겨 앉는 자리입니다.

선선한 가을 아침, 새 무리가 전선 위에 앉아 있습니다. 첫 번째 전선에는 0,1,…,n−10, 1, \dots, n-1로 번호가 붙은 nn개의 연속된 자리가 있습니다. 두 번째 전선에도 같은 방식으로 번호가 붙은 nn개의 자리가 있습니다.

처음에는 첫 번째 전선의 일부 자리에 새가 있고(새가 없는 자리도 있을 수 있습니다), 두 번째 전선은 비어 있습니다. 각 새는 두 번째 전선에서 가고 싶은 목표 자리를 정해 두고 있습니다. 같은 자리에서 출발하는 새들의 목표 자리는 서로 다릅니다.

모든 새가 동시에 목표 자리를 향해 날아갑니다. 각 새는 출발 자리와 목표 자리를 잇는 직선 선분을 따라 날아갑니다.

두 선분이 교차하면 그 두 새는 부딪힐 수 있습니다. 이렇게 순서 없이 짝지은 새 두 마리를 위험한 쌍이라고 합니다.

예를 들어 2번 자리의 새가 1번 자리로, 1번 자리의 새가 2번 자리로 가려고 하면 두 경로는 교차합니다.

출발 자리가 같거나 목표 자리가 같은 새들의 쌍은 위험한 쌍이 아닙니다.

위험한 쌍의 개수를 구하세요.

입력

첫 줄에 정수 nn (1≤n≤2⋅1051 \le n \le 2 \cdot 10^5)이 주어집니다. 이는 각 전선의 자리 수입니다.

이어지는 nn개의 줄은 각 출발 자리에 있는 새들의 목표 자리를 나타냅니다. ii번째 줄은 정수 pip_i (0≤pi≤n0 \le p_i \le n)로 시작하며, 이는 ii번 자리에 있는 새의 수입니다. 그 뒤에 서로 다른 정수 pip_i개 qi,1,…,qi,piq_{i,1}, \dots, q_{i,p_i} (0≤qi,j≤n−10 \le q_{i,j} \le n-1)가 나오며, 이들이 그 새들의 목표 자리입니다.

모든 pip_i의 합은 2⋅1052 \cdot 10^5을 넘지 않습니다.

출력

위험한 쌍의 개수를 나타내는 정수 하나를 한 줄에 출력합니다.

예제1

  1. 예제 1

    입력
    3
    2 1 2
    1 0
    1 1
    
    예상 출력
    3