Incompatible Cow Pairs

Farmer John has \(N\) cows (\(2\le N\le 5\times 10^4\)). Each cow has a list of her 5 favorite ice cream flavors. Each flavor is represented by a positive integer \(ID\) (with \(ID\le 10^6\)). Two cows can peacefully coexist if they share at least one flavor. Otherwise, they are incompatible. Your task is to count the number of unordered pairs of cows that are incompatible (i.e. they do not share any common flavor).

Input Format: The first line contains the integer \(N\). The next \(N\) lines each contain 5 space-separated integers representing the flavors for a cow. Note that the list for each cow may be in any order.

Output Format: Output a single integer: the number of incompatible cow pairs.

Hint: It might be easier to first count the number of compatible (harmonious) pairs and then subtract from the total pairs \(\binom{N}{2}\). To efficiently count compatible pairs, consider using the inclusion-exclusion principle over all non-empty subsets of each cow's flavor list.

inputFormat

The input begins with a line containing the integer \(N\). Each of the next \(N\) lines contains 5 space-separated integers representing one cow's favorite ice cream flavor \(ID\)s.

outputFormat

Output a single integer indicating the number of incompatible pairs of cows.

sample

3
1 2 3 4 5
1 2 3 6 7
1 6 7 8 9

0