この問題は全探索により解くことができます。

積を直接管理すると非常に大きな値となるため、素因数分解した形で管理します。

\(P_i,Q_i\) の最大値を \(M\) として、\(M\) 以下の整数全てに対する素因数分解の前計算が \(O(M^2)\) 、全探索が各選び方に対して \(O(N\log\log M+M)\) かかることから計算量は \(O(M^2+2^N(N\log\log M+M))\) となります。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int>p(n),q(n);
  for(int i=0;i<n;i++)cin >> p[i] >> q[i];

  // 素因数分解の前計算
  vector<unordered_map<int,int>>a(101);
  for(int i=2; i<=100; i++){
    unordered_map<int,int>d;
    int ii = i;
    for(int j=2; j<=100; j++){
      while(ii % j == 0){
        ii /= j;
        d[j]++;
      }
    }
    a[i] = d;
  }
  
  int ans = 100;
  for(int s=0; s<1<<n; s++){
    if(__builtin_popcount(s) <= 1){
      continue;
    }
    vector<int>x(100), y(100);
    for(int i=0; i<n; i++){
      if(s & (1<<i)){
        for(auto[k,v]: a[p[i]]){
          x[k] += v;
        }
        for(auto[k,v]: a[q[i]]){
          y[k]+=v;
        }
      }
    }
    if(x == y){
      ans = min(ans, __builtin_popcount(s));
    }
  }
  
  if(ans == 100){
    cout << -1 << endl;
  }else{
    cout << ans << endl;
  }
}

なお、python では多倍長整数を特に工夫無く扱えるため、積を直接管理することでも解くことができます。

実装例 (Python)

N = int(input())
P, Q = [], []
for _ in range(N):
  p, q = map(int, input().split())
  P.append(p)
  Q.append(q)

ans = 100
for s in range(1<<N):
  if s.bit_count() <= 1:
    continue
  x, y = 1, 1
  for i in range(N):
    if s & (1<<i):
      x *= P[i]
      y *= Q[i]
  if x == y:
    ans = min(ans, s.bit_count())

if ans == 100:
  print(-1)
else:
  print(ans)