Minimum Additional Transfer Stations

Little Y is an OIer who loves traveling. One day, she arrived in a new city and took the subway because she was unfamiliar with the local transportation system. In this city, every subway line can be regarded as a curve drawn on the plane. At each intersection of two lines a transfer station is set up. It is known that no line is circular and no line intersects itself. Moreover, any two distinct lines intersect at one or more isolated points (with no overlapping segments), and no three lines have a common intersection point. (For example, intersections as shown in the figure below do not occur.)

Little Y was riding line 0 and passed through n transfer stations along the way. At each station, she recorded the set of subway line numbers (other than 0) that can be transferred to. She observed that for every other line, there are at most 2 transfer stations with line 0. Our task is to determine the minimum number of transfer stations other than those on line 0 in the entire city.

A key observation is as follows. For each line (not line 0) that appears in Little Y's record, let the positions (indices) where the line appears on line 0 be noted. If a line appears twice, then it forms a chord connecting its 2 appearances on line 0. Two such chords, say for lines L and M, will necessarily intersect (i.e. there will be an extra transfer station where line L meets line M) if and only if their endpoints are interwoven, i.e. if the endpoints of L are at positions \(a < b\) and those of M are at positions \(c < d\) such that either \(a < c < b < d\) or \(c < a < d < b\). Lines that appear only once do not force any extra intersections. The answer is the total number of intersections among chords (lines that appear twice) in this sense.

Input Format: The first line contains an integer n denoting the number of transfer stations on line 0 that Little Y passed. Each of the following n lines describes a transfer station. Each transfer station is given in one line starting with an integer k (the number of lines available for transfer at that station), followed by k positive integers representing the subway line numbers (other than 0). It is guaranteed that each line number appears at most twice in the entire input.

Output Format: Output a single integer: the minimum number of transfer stations (excluding those on line 0) in the city.

Constraints:

• 1 ≤ n ≤ 10⁵
• The total number of line occurrences is at most 2 × 10⁵.

Note: You need to count the number of pairs of lines (that appear exactly twice) whose appearances on line 0 are interwoven. Each such pair forces an extra transfer station (intersection) outside line 0.

inputFormat

The input begins with an integer n on the first line, representing the number of transfer stations on line 0 that Little Y passed. In the following n lines, each line starts with an integer k (the number of available transfer lines at that station), followed by k space-separated positive integers (the subway line numbers, not including 0).

outputFormat

Output a single integer, the minimum number of transfer stations in the city excluding the n stations on line 0.

sample

3
2 1 2
2 2 3
2 1 3

0