P5123 [USACO18DEC] Cowpatibility G

On 2025/4/9, two groups of hack testdata were added (@Starrykiller).

Research shows that one factor matters more than anything else in whether two cows can get along as friends—whether they like the same ice cream flavor. Farmer John has $N$ cows ($2 \le N \le 5 \times 10^4$). Each cow lists her five favorite ice cream flavors. To make the list more concise, each possible flavor is represented by a positive integer $\texttt{ID}$ not exceeding $10^6$. If two cows' lists share at least one common ice cream flavor, then they can get along. Please compute the number of pairs of cows that cannot get along.

The first line contains $N$. The next $N$ lines each contain $5$ integers (all distinct), representing one cow’s favorite ice cream flavors.

Output the number of pairs of cows that cannot get along.

Here, cow $4$ cannot get along with any of cows $1$, $2$, or $3$, and cow $1$ and cow $3$ also cannot get along. Translated by ChatGPT 5