分数: 400 分
问题陈述
高桥有 N 卡。的 i第一张牌 (1 \leq i \leq N) 有一个正整数 正面写有 P_i 和一个正整数 背面写有 Q_i 。
高桥想要选择 这些卡片中的 2 或多张卡片。让 S (S \subseteq \{1, 2, \ldots, N\}, |S| \geq 2) 是所选卡片的索引集。判断是否存在这样的 S 其中所选卡片正面写的整数的乘积等于背面写的整数的乘积,即
\prod_{i \in S} P_i = \prod_{i \in S} Q_i
如果这样 S 存在,输出最小值 |S| 其中 S 满足条件。如果没有这样的 S 存在,输出 -1.
约束
- 2 \leq N \leq 22
- 1 \leq P_i \leq 100
- 1 \leq Q_i \leq 100
- 所有输入值均为整数。
输入
N P_1 Q_1 P_2 Q_2 \vdots P_N Q_N
第一行包含一个整数 N 代表卡片数量。以下每一项 N 行, i第行(1 \leq i \leq N),包含整数 正面写有 P_i 和整数 Q_i 写在背面 i第一张卡,以空格分隔。
输出
如果一组 S 满足条件存在,输出最小值 |S| 在一行中。如果不存在这样的集合,则输出 -1.
示例输入 1
3 2 3 3 2 5 5
示例输出 1
2
示例输入 2
3 2 1 4 1 8 1
示例输出 2
-1
示例输入 3
8 2 3 3 5 5 2 7 1 11 1 13 1 17 1 19 1
示例输出 3
3
示例输入 4
15 2 3 3 5 5 7 7 2 11 1 13 1 17 1 19 1 23 1 29 1 31 1 37 1 41 1 43 1 47 1
示例输出 4
4
示例输入 5
2 5 5 3 3
示例输出 5
2