D - Card Stacking Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は N 枚のカードを持っています。i 番目（1 \leq i \leq N）のカードの表面には正の整数 P_i が、裏面には正の整数 Q_i が書かれています。

高橋君はこれらのカードの中から 2 枚以上を選びたいと考えています。選んだカードの番号の集合を S（S \subseteq \{1, 2, \ldots, N\}、|S| \geq 2）とします。このとき、選んだカードの表面に書かれた整数の積と裏面に書かれた整数の積が等しい、すなわち

\prod_{i \in S} P_i = \prod_{i \in S} Q_i

が成り立つような 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

1 行目には、カードの枚数を表す整数 N が与えられる。続く N 行の i 行目（1 \leq i \leq N）には、i 番目のカードの表面に書かれた整数 P_i と裏面に書かれた整数 Q_i がスペース区切りで与えられる。

出力

条件を満たす集合 S が存在する場合、|S| の最小値を 1 行で出力せよ。存在しない場合は -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

Score : 400 pts

Problem Statement

Takahashi has N cards. The i-th card (1 \leq i \leq N) has a positive integer P_i written on its front side and a positive integer Q_i written on its back side.

Takahashi wants to select 2 or more cards from among these cards. Let S (S \subseteq \{1, 2, \ldots, N\}, |S| \geq 2) be the set of indices of the selected cards. Determine whether there exists such an S where the product of the integers written on the front sides of the selected cards equals the product of the integers written on the back sides, that is,

\prod_{i \in S} P_i = \prod_{i \in S} Q_i

If such an S exists, output the minimum value of |S| among all S satisfying the condition. If no such S exists, output -1.

Constraints

  • 2 \leq N \leq 22
  • 1 \leq P_i \leq 100
  • 1 \leq Q_i \leq 100
  • All input values are integers.

Input

N
P_1 Q_1
P_2 Q_2
\vdots
P_N Q_N

The first line contains an integer N representing the number of cards. Each of the following N lines, the i-th line (1 \leq i \leq N), contains the integer P_i written on the front side and the integer Q_i written on the back side of the i-th card, separated by a space.

Output

If a set S satisfying the condition exists, output the minimum value of |S| in a single line. If no such set exists, output -1.

Sample Input 1

3
2 3
3 2
5 5

Sample Output 1

2

Sample Input 2

3
2 1
4 1
8 1

Sample Output 2

-1

Sample Input 3

8
2 3
3 5
5 2
7 1
11 1
13 1
17 1
19 1

Sample Output 3

3

Sample Input 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

Sample Output 4

4

Sample Input 5

2
5 5
3 3

Sample Output 5

2