#include #include #include #include #include using namespace std; typedef long long ll; ll const flag=(1ll<<50ll); ll a[2500],b[2500]; map assign,from; queue todo; int main(){ int n; cin>>n; for (int i=0; i>a[i]>>b[i]; for (int changed=1; changed--; from.clear()){ for (int i=n; i--;) if (not assign.count(i^flag)) todo.push(from[i^flag]=i^flag); while (not todo.empty()){ ll x=todo.front(); todo.pop(); if (x>=flag){ x^=flag; if (changed) continue; for (ll v: {a[x]+b[x],a[x]-b[x],a[x]*b[x]}) if (not from.count(v)){ from[v]=(x^flag); todo.push(v); } } else if (not assign.count(x)){ vector path={x}; while (from.count(path.back()) and path.back()!=from[path.back()]){ path.push_back(from[path.back()]); from.erase(path[path.size()-2]); } if (from.count(path.back()) and path.back()==from[path.back()]) for (int z=0; z