← 返回题目列表

AtCoder · awc0060_d

D. 卡片堆叠

中文机器翻译题面 查看原题

分数: 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