Popular Product Pairs

Popular Product Pairs

You are given information about several transactions in a store. In each transaction, a customer buys one or more products. Your task is to find all pairs of products that occur together in strictly more than k transactions. Each transaction is given as a line where the first number indicates the number of products bought in that transaction, followed by the product IDs.

For example, if a pair of products appears together in 2 transactions and k is 1, then the pair is considered popular because 2 > 1. The output should list the popular pairs in ascending order, each pair on a new line with the two product IDs separated by a space. If no such pair exists, output "No popular pairs".

Note: In counting pairs, each transaction is considered independently. Pairs should be formed only from distinct products in the transaction and counted once per transaction regardless of ordering.

Formally, if the number of transactions is T and for each transaction i a subset of products P_i is bought, then a pair \((x, y)\) is popular if \[ \#\{ i \mid x, y \in P_{i} \} > k. \]

inputFormat

Input Format

The input is read from stdin and consists of:

1. A single line containing two integers p (the total number of products) and t (the number of transactions).
2. t lines follow, each representing a transaction. Each transaction starts with an integer m (the number of products in the transaction) followed by m integers indicating the product IDs.
3. A single line containing an integer k, the threshold frequency. A pair is considered popular if it appears in more than k transactions.

outputFormat

Output Format

If there exist popular pairs, output each popular pair on a separate line with the two product IDs separated by a space, in ascending order (first by the first product and then by the second). If no popular pairs exist, output a single line with the text "No popular pairs".

Output is written to stdout.

## sample

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

1 2
2 3

</p>