Most Common Item Pair

You are given a list of transactions. Each transaction is a list of item IDs. Your task is to determine the pair of items that occur together most frequently. If no valid pair exists, output None.

For each transaction, generate all unique pairs \((i, j)\) with \(i < j\) and count their occurrences across all transactions. If multiple pairs have the same maximum frequency, choose the lexicographically smallest pair. Mathematically, given transactions \(T = \{t_1, t_2, \ldots, t_n\}\), for each transaction \(t\) define the set of pairs as \[ P(t) = \{(a, b) \mid a, b \in t,\ a < b\} \] and find the pair with the maximum frequency over all \(P(t)\)s.

inputFormat

The first line of input contains a single integer \(n\) representing the number of transactions. The following \(n\) lines each contain a space-separated list of integers representing the item IDs in that transaction (a transaction may be empty).

outputFormat

If a valid pair exists, output the two item IDs of the most common pair in increasing order, separated by a space. If no pair exists, output None.

5
1 2 3
1 2 4
1 2
2 3
2 3 4

1 2